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;
}
}
