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.
Solution:
/**
* 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 {
public RandomListNode copyRandomList(RandomListNode head) {
RandomListNode cur = head;
while(cur!=null){
RandomListNode clone = new RandomListNode(cur.label);
clone.next = cur.next;
clone.random = cur.random;
cur.next = clone;
cur = cur.next.next;
}
cur = head;
while(cur!=null){
if(cur.next.random!=null) cur.next.random = cur.random.next;
cur = cur.next.next;
}
RandomListNode dummy = new RandomListNode(0);
cur = head;
dummy.next = cur==null ? null : cur.next;
while(cur!=null){
RandomListNode tmp = cur.next.next;
cur.next.next = tmp==null ? null : tmp.next;
cur.next = tmp;
cur = cur.next;
}
return dummy.next;
}
}