复制含有随机指针节点的链表

【题目】 一种特殊的链表节点类描述如下：
public class Node { public int value; public Node next; public
Node rand;
public Node(int data) { this.value = data; }
}
Node类中的value是节点值，next指针和正常单链表中next指针的意义
一 样，都指向下一个节点，rand指针是Node类中新增的指针，这个指
针可 能指向链表中的任意一个节点，也可能指向null。 给定一个由
Node节点类型组成的无环单链表的头节点head，请实现一个 函数完成
这个链表中所有结构的复制，并返回复制的新链表的头节点。

进阶：
不使用额外的数据结构，只用有限几个变量，且在时间复杂度为 O(N)
内完成原问题要实现的函数。

解题思路

原问题的思路

（1） 用哈希表的结构，将原链表的节点和它的拷贝节点以键值对形式放到哈希表中，即创建一个哈希表，它的<key, value>为<原节点,拷贝节点>
（2）通过哈希表的get方法，在拥有当前节点以后我们可以得到它的拷贝节点，同时，我们得到当前节点的next指针所指向的节点以后，可以得到next指针的拷贝节点。rand节点同理。
（3）把当前节点的拷贝节点的next指针，指向当前节点的next指针所指向的节点的拷贝节点，rand指针同理。
（4）循环遍历这个链表，重复第3步的操作，我们就可以完成对原链表中所有结构的复制。

• Java代码如下：

public static Node copyListWithRand1(Node head) {
        HashMap<Node, Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null) { //把所有节点和它对应的拷贝节点放到哈希表
            map.put(cur, new Node(cur.value));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) { // 从哈希表中取出当前节点A对应的拷贝节点A'
            // 将A'的next指针指向A的next指针所指向的节点的拷贝节点，rand指针同理
            map.get(cur).next = map.get(cur.next);
            map.get(cur).rand = map.get(cur.rand);
            cur = cur.next;
        }
        return map.get(head);
    }

进阶问题的思路

其实我觉得我应该画个图，因为这个东西用语言表达起来特别费劲，但是我没有时间，所以就先这样吧。

（1）遍历原链表，使得让原链表每一个节点的next指针指向它的拷贝节点，它的拷贝节点的next指针指向原节点的next节点。拷贝时要注意顺序，先用一个临时节点存放原节点的next节点，然后原节点的next指针指向它的拷贝节点，再把拷贝节点的next指针指向这个临时节点。
（2）经过第1步以后，这个链表的结构变成了A -> A' -> B -> B' -> C -> C' -> ......但是原链表所有节点的rand指针没有发生变化。
这时，将拷贝节点的rand指针指向当前节点A的rand指针所指向的节点N的下一个节点N'，因为N'就是当前节点A的rand指针所指向的N的拷贝节点，即A'.rand -> A.rand.next，但是要注意，当前节点的rand节点可能指向null，所以在设置前先要进行判断。
（3）经过第2步以后，拷贝节点的rand指针都已经设置好了，就差把原节点和拷贝节点从这个大的链表分开了。很简单，当前节点的next的next指向的就是它原本的next节点，拷贝节点同理。

• Java代码如下：

public static Node copyListWithRand2(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        Node next;
        // 将原链表的节点的next指针指向拷贝节点，拷贝节点的next指针指向原节点的next节点
        while (cur != null) {
            next = cur.next;
            cur.next = new Node(cur.value);
            cur.next.next = next;
            cur = next;
        }
        cur = head;
        Node curCopy;
        // 设置拷贝节点的rand指针
        while (cur != null) {
            next = cur.next.next;
            curCopy = cur.next;
            curCopy.rand = cur.rand != null ? cur.rand.next : null;
            cur = next;
        }
        Node res = head.next;
        cur = head;
        // 将两个链表分开
        while (cur != null) {
            next = cur.next.next;
            curCopy = cur.next;
            cur.next = next;
            curCopy.next = next != null ? next.next : null;
            cur = next;
        }
        return res;
    }