Copy List with Random Pointer

 1 /**
 2  * Definition for singly-linked list with a random pointer.
 3  * class RandomListNode {
 4  *     int label;
 5  *     RandomListNode next, random;
 6  *     RandomListNode(int x) { this.label = x; }
 7  * };
 8  */
 9 public class Solution {
10     /**
11      * @param head: The head of linked list with a random pointer.
12      * @return: A new head of a deep copy of the list.
13      */
14     public RandomListNode copyRandomList(RandomListNode listHead) {
15         if (listHead == null) return listHead;
16         RandomListNode current = listHead;
17         // add duplicate nodes
18         while(current != null) {
19             RandomListNode node = new RandomListNode(current.label);
20             node.next = current.next;
21             current.next = node;
22             current = current.next.next;
23         }
24         
25         // set random pointer
26         current = listHead;
27         while (current != null) {
28             if (current.random != null) {
29                 current.next.random = current.random.next;
30             }
31             current = current.next.next;
32         }
33         
34         // restore and detach
35         RandomListNode newHead = listHead.next;
36         RandomListNode current1 = listHead;
37         RandomListNode current2 = newHead;
38         while (current1 != null) {
39             current1.next = current2.next;
40             current1 = current1.next;
41             if (current1 != null) {  // very important, cannot remove it.
42                 current2.next = current1.next;
43             }
44             current2 = current2.next;
45         }
46         return newHead;
47     }
48 }