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.
Return a deep copy of the list.
一道相对比较复杂的链表题。第一种思路是使用HashMap来存储原来的节点和新生成的节点之间的对应关系，通过这个对应关系来恢复新生成的节点的random所指向的节点。这种方法的空间复杂度为O(n)。
public RandomListNode copyRandomList(RandomListNode head) {
if(head == null) return head;
HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
RandomListNode dummy = new RandomListNode(0);
RandomListNode temp1 = head, temp2 = dummy;
while(temp1 != null) {
RandomListNode node = new RandomListNode(temp1.label);
map.put(temp1, node);
temp2.next = node;
temp2 = temp2.next;
temp1 = temp1.next;
}
temp1 = head; temp2 = dummy.next;
while(temp1 != null) {
if(temp1.random != null) {
temp2.random = map.get(temp1.random);
}
temp1 = temp1.next;
temp2 = temp2.next;
}
return dummy.next;
}
另一种方法比较巧妙，通过改变原来的链表，即将新生产的节点插入在原来的节点后面，然后第二遍扫描的时候来恢复random的值，然后第三遍扫描将原来的节点和新生产的节点分离，从而得到一个deep copy原来的链表。
public RandomListNode copyRandomList(RandomListNode head) {
if(head == null) return head;
RandomListNode temp = head;
while(temp != null) {
RandomListNode node = new RandomListNode(temp.label);
node.next = temp.next;
temp.next = node;
temp = node.next;
}
temp = head;
while(temp != null) {
if(temp.random != null) {
temp.next.random = temp.random.next;
}
temp = temp.next.next;
}
RandomListNode nhead = head.next, ntemp = head.next;
temp = head;
while(head != null) {
temp.next = ntemp.next;
temp = temp.next;
if(temp == null) break;
ntemp.next = temp.next;
ntemp = ntemp.next;
}
return nhead;
}
