复杂链表的复制

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
public class Solution {
    public RandomListNode Clone(RandomListNode head)
    {
        if(head == null){
            return null;
        }
        RandomListNode l1 = head;
        RandomListNode l2 = null;
        while(l1 != null){
            l2 = new RandomListNode(l1.label);
            l2.next = l1.next;
            l1.next = l2;
            l1 = l1.next.next;
        }
        l1 = head;
        while(l1 != null){
            if(l1.random != null){
                l1.next.random = l1.random.next;
            }
            l1 = l1.next.next;
        }
        l1 = head;
        RandomListNode l2_head = l1.next;
        while(l1 != null){
            l2 = l1.next;
            l1.next = l2.next;
            if(l2.next != null){
                l2.next = l2.next.next;
            }
            l1 = l1.next;
        }
        return l2_head;
    }
}

题目

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

思路

大部分人首先想到的可能是先复制复杂指针的label和next，然后再查找random并更新。查找random又分为两种，一种是每次都从头查找，时间复杂度为O(n^2)；另一种是空间换时间，复制label和next的同时建立一个hash表来存放新旧复杂指针的对应关系，所以后续只需一步就能找到random，算法时间复杂度为O(n)。

我们这里将复杂链表的复制过程分解为三个步骤。在写代码的时候我们每一步定义一个函数，这样每个函数完成一个功能，整个过程的逻辑也就非常清晰明了了。

我们这里采用三步：

第一步：复制复杂指针的label和next。但是这次我们把复制的结点跟在元结点后面，而不是直接创建新的链表；

第二步：设置复制出来的结点的random。因为新旧结点是前后对应关系，所以也是一步就能找到random；

第三步：拆分链表。奇数是原链表，偶数是复制的链表。

有图思路更清晰：

hashmap方式

 

public Node copyRandomList(Node head) {
    if (head == null) {
        return null;
    }
    Map<Node, Node> map = new HashMap<>();
    Node node = head;
    while (node != null){
        map.put(node, new Node(node.val, null, null));
        node = node.next;
    }
    node = head;
    while (node != null){
        map.get(node).next = map.get(node.next);
        map.get(node).random = map.get(node.random);
        node = node.next;
    }
    return map.get(head);
}

尾复制链表

public static Node copyRandomList(Node head) {
    if (head == null) {
        return null;
    }
    Node l1 = head;
    Node l2 = null;
    //生成所有的节点，并且分别插入到原有节点的后边
    while (l1 != null) {
        l2 = new Node();
        l2.val = l1.val;
        l2.next = l1.next;
        l1.next = l2;
        l1 = l1.next.next;
    }
    //更新插入节点的 random
    l1 = head;
    while (l1 != null) {
        if (l1.random != null) {
            l1.next.random = l1.random.next;
        }
        l1 = l1.next.next;
    }

    l1 = head;
    Node l2_head = l1.next;
    //将新旧节点分离开来
    while (l1 != null) {
        l2 = l1.next;
        l1.next = l2.next;
        if (l2.next != null) {
            l2.next = l2.next.next;
        }
        l1 = l1.next;
    }
    return l2_head;
}

主函数

public static void main(String[] args) {
    Node head = null;
    head = new Node();
    head.val = 1;
    head.next = new Node();
    head.next.val = 2;
    head.next.next = new Node();
    head.next.next.val =3;
    head.next.next.next = new Node();
    head.next.next.next.val =4;
    head.next.next.next.next = new Node();
    head.next.next.next.next.val = 5;
    head.next.next.next.next.next = new Node();
    head.next.next.next.next.next.val = 6;
    head.random = head.next.next.next.next.next; // 1 -> 6
    head.next.random = head.next.next.next.next.next; // 2 -> 6
    head.next.next.random = head.next.next.next.next; // 3 -> 5
    head.next.next.next.random = head.next.next; // 4 -> 3
    head.next.next.next.next.random = null; // 5 -> null
    head.next.next.next.next.next.random = head.next.next.next; // 6 -> 4
    Node res = copyRandomList(head);
    printRandLinkedList(res);
}

打印函数

public static void printRandLinkedList(Node head) {
    Node cur = head;
    System.out.print("order:");
    while (cur != null) {
        System.out.print(cur.val + " ");
        cur = cur.next;
    }

    cur = head;
    System.out.println();
    System.out.print("random:");
    while (cur != null) {
        System.out.print(cur.random == null ? "- " : cur.random.val + " ");
        cur = cur.next;
    }
    System.out.println();
}