138. 复制带随机指针的链表

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的 深拷贝。
我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

image.png

思路

本题难点是找到原始节点的random节点
1 第一遍遍历，深拷贝每一个节点，使原始节点的next指向它的深拷贝节点，深拷贝节点指向原始节点的原始next节点。这样每个原始节点的next节点都是它的深拷贝节点
即n1->n1'->n2->n2'->null
2 第二遍遍历，使深拷贝节点的random节点指向原始节点的random节点的next节点（也就是原始节点random的深拷贝节点）
3 断开两个链表

代码

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null){
            return null;
        }
        //1 将所有节点，深拷贝出一个节点，放在该节点后。注意这样就可以通过p.next找到节点的深拷贝节点
        Node p = head;
        while (p != null){
            Node cp = new Node(p.val);
            cp.next = p.next;
            p.next = cp;
            p = p.next.next;
        }
        //2 给深拷贝节点的random复制
        p = head;
        while (p != null){
            if(p.random != null) {
                p.next.random = p.random.next;
            }else {
                p.next.random = null;
            }
            p = p.next.next;
        }

        //3 断开两个链表
        p = head;
        Node p2 = head.next;
        Node newHead = p.next;
        while (p2.next != null){
            p.next = p2.next;
            p = p.next;
            p2.next = p.next;
            p2 = p2.next;
        }
        p.next = null;
        return newHead;
    }
}