138. Copy List with Random Pointer Leetcode Java

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.

/**

 * Definition for singly-linked list with a random pointer.

 * class RandomListNode {

 *     int label;

 *     RandomListNode next, random;

 *     RandomListNode(int x) { this.label = x; }

 * };

 */

Solution:

1, HashMap

This solution is very intuitive. Basically, we build a hashmap to mapping the given nodes to the created nodes. When we traversal the list, if cur.random is in the map, we put the created newCur.random = map.get(cur.random), otherwise create a new node with cur.random.lable and map it to cur.random. We do the same thing for cur.next. So when we finish the traversal, we will get a copy of the list with random pointer.
Time complexity: O(n)  O(n) extra space.

  public RandomListNode copyRandomList(RandomListNode head) {  
    if(head==null) return null;  
    RandomListNode newHead=new RandomListNode(head.label);  
    HashMap<RandomListNode, RandomListNode> map=new HashMap<RandomListNode,RandomListNode>();  
    map.put(head,newHead);  
    RandomListNode cur=head;  
    RandomListNode newCur=newHead;  
    while(cur!=null){  
      if(cur.random!=null){  
        if(map.containsKey(cur.random)) newCur.random=map.get(cur.random);  
        else{  
          RandomListNode newNode=new RandomListNode(cur.random.label);  
          newCur.random=newNode;  
          map.put(cur.random,newNode);  
        }  
      }  
      if(cur.next!=null){  
        if(map.containsKey(cur.next)) newCur.next=map.get(cur.next);  
        else{  
          RandomListNode newNode=new RandomListNode(cur.next.label);  
          newCur.next=newNode;  
          map.put(cur.next,newNode);  
        }  
      }  
      cur=cur.next;  
      newCur=newCur.next;  
    }  
    return newHead;  
   }  

2, two pointer
This is solution is very clever. We create the copy of given node cur,  and set the image as the real.next: copied(Cur)=cur.next; Then we can connect the random pointer simply by setting cur.next.random=cur.random.next. which equivalent to set copied(Cur).random=copied(Cur.random). The last step is to separate the copied list from original list. What I did is use a counter, for odd counter it means the processing node is from original list, so cur.next= copied(cur).next. For even counter it means the processing node is from copied list. We separate the list one node a time from original list and copied list in turn.
Time complexity: O(n)  no extra space.

  public RandomListNode copyRandomList(RandomListNode head) {  
    if(head==null) return null;  
    RandomListNode cur=head;  
    while(cur!=null){  
      RandomListNode temp=new RandomListNode(cur.label);  
      temp.next=cur.next;  
      cur.next=temp;  
      cur=temp.next;  
    }  
    cur=head;  
    while(cur!=null){  
      if(cur.random!=null){  
        cur.next.random=cur.random.next;  
      }  
      cur=cur.next.next;  
    }  
    RandomListNode newHead=head.next;  
    cur=head;  
    RandomListNode newCur=newHead;  
    int i=1;  
    while(cur!=null){  
      if(i%2==1){  
        cur.next=newCur.next;  
        cur=cur.next;  
      }  
      else{  
        newCur.next=cur.next;  
        newCur=newCur.next;  
      }  
      i++;  
    }  
    return newHead;  
   }