### 题目

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

class RandomListNode {
int label;
RandomListNode next, random;
RandomListNode(int x) { this.label = x; }
};


Return a deep copy of the list.

！注意：前提条件式每个节点的label值是唯一的。

### 使用一个额外的Map存放所有节点。时间复杂度 $O(n)$，额外空间 $O(n)$

Next Chain = 1->2->3->4
Random Chain = [ [1->3], [2->4], [3->1], [4->1] ]


#### 代码

/**
* Definition for singly-linked list with a random pointer.
* class RandomListNode {
*     int label;
*     RandomListNode next, random;
*     RandomListNode(int x) { this.label = x; }
* };
*/
public class Solution {
RandomListNode dummy = new RandomListNode(0);
Map<Integer,RandomListNode> memo = new HashMap<>();
RandomListNode copyCur = dummy;
while (cur != null) { // copy next chain
RandomListNode copyNode = new RandomListNode(cur.label);
memo.put(cur.label,copyNode);
copyCur.next = copyNode;
cur = cur.next;
copyCur = copyCur.next;
}
copyCur = dummy.next;
while (cur != null) { // copy random chain
if (cur.random != null) {
copyCur.random = memo.get(cur.random.label);
}
cur = cur.next;
copyCur = copyCur.next;
}
return dummy.next;
}
}


### 不使用额外空间

1. 拷贝所有节点，并插在原节点后面，变成1->1->2->2->3->3->4->4
2. 第二次遍历，补全所有random引用。
3. 第三次遍历，把original listcopy list剥离成两个独立的链表。

#### 代码

public class Solution {
RandomListNode cur = head, dummy = new RandomListNode(0), copyCur = dummy;
while (cur != null) { // copy next chain, and insert new node right after the original node
RandomListNode newNode = new RandomListNode(cur.label);
newNode.next = cur.next;
cur.next = newNode;
copyCur.next = newNode;
copyCur = newNode.next;
cur = newNode.next;
}
while (cur != null) { // 拷贝random
copyCur = cur.next;
if (cur.random != null) {
copyCur.random = cur.random.next; // 拷贝random指针
}
cur = copyCur.next;
}
while (cur != null) { // 从original list上剥离copy list
copyCur = cur.next;
cur.next = copyCur.next;
if (cur.next != null) {
copyCur.next = cur.next.next;
} else {
copyCur.next = null;
}
cur = cur.next;
}
return dummy.next;
}
}