题目.png
解决思路
在原有链表中，进行节点的复制，即每个节点的next指向其复制的节点，复制的新节点next指向下一个旧节点；如下所示: old node1 -> new node1 -> old node2 -> new node2；
从head开始，每两个节点，前一个为old，后一个为new，new.random 对应 old.random.next，完成所有复制节点的random复制；
注意 old.random 可能为null。
将新旧链表拆开即可。
注意，不能在遍历设置random的同时，去拆开链表，因为random可能指向链表前面的元素，拆开后不能完成random设置。
example：
class Solution {
public Node copyRandomList(Node head) {
if (head == null) return null;
for (Node cur = head; cur != null;) {
Node temp = new Node(cur.val, cur.next, null);
cur.next = temp;
cur = temp.next;
}
for (Node cur = head; cur != null;) {
if (cur.random != null) {
cur.next.random = cur.random.next;
}
cur = cur.next.next;
}
Node result = head.next;
for (Node cur = head;;) {
Node temp = cur.next;
cur.next = temp.next;
cur = cur.next;
if (cur == null) break;
temp.next = cur.next;
}
return result;
}
}
