leetcode: Copy List with Random Pointer

Question specification:
A linked list is given such that each node contains an additional random pointer which should point to any node in the list or all.

More: Do not assume the label value of each node is distinct.

Solution1: (2 pass)

1. start from head, follow next pointer, create a list via new.
2. start from head, point random pointer to correct node.

Analysis: Step2 is quite time consuming. For each node, in order to find its correct random, need to start checking from the very beginning--head. In worst case, for node whose position is n in the list, it takes n movement to find its random.

Solution2: 

The difficulty is how to point random to correct node.  Two imagination can help improving step2:

• If we can quickly know which node should the random node point to...
• If we have random access to all the node in the list...

Using HashMap and ArrayList together can help realizing these two imaginations. When iterate over the original list, we can put each node into HashMap, and assign unique identifier--increasing integer--to each node. At the same time,  add the newly created/cloned node into an ArrayList. 

• HashMap: <Original node, integerValue>
• ArrayList: <Clone of original node>

The relationship between the HashMap and the ArrayList is:  the index for cloned node (in ArrayList)  equals to the integerValue of original node (in HashMap).

Now for each random node,we can find its associated integer value by query HashMap. Then the clone of this random node can be found by indexing ArrayList.

Also, we do not need to separate the two steps mentioned in Solution1.

public class Solution {
    
     public RandomListNode copyRandomList(RandomListNode head) {
        
        if(head == null) return null;
        
        RandomListNode current = head;
        RandomListNode head2 = new RandomListNode(head.label);
        RandomListNode current2 = head2;
        
        HashMap  all = new HashMap();
        ArrayList  list = new ArrayList ();
        
        all.put(head, 0);
        list.add(head2);
        
        //copy list 
        int i = 1;
        while(current.next != null){
            //copy current.random
            if(current.random != null){
                if(!all.containsKey(current.random)){
                    all.put(current.random, i++);
                    RandomListNode tempRandom = new RandomListNode(current.random.label);
                    current2.random = tempRandom;
                    list.add(tempRandom);
                }
                else{
                    int pos = all.get(current.random);
                    current2.random = list.get(pos);
                }
            }
            //copy current.next;
            
            if(!all.containsKey(current.next))
            {
                all.put(current.next, i++);
                RandomListNode temp = new RandomListNode(current.next.label);
                current2.next = temp;
                list.add(temp);
            }else{
                int pos = all.get(current.next);
                current2.next = list.get(pos);
            }
            current = current.next;
            current2 = current2.next;
        }
        
        if(current.random != null){
                if(!all.containsKey(current.random)){
                    all.put(current.random, i++);
                    RandomListNode tempRandom = new RandomListNode(current.random.label);
                    current2.random = tempRandom;
                    list.add(tempRandom);
                }
                else{
                    int pos = all.get(current.random);
                    current2.random = list.get(pos);
                }
            }
        
        return head2;
    }
    
}