Leetcode 138 Copy List with Random Pointer

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 1: use graph copy method, it can deal with the random list even it has loop. Below is an example of BFS.

 public class Solution {  
   public RandomListNode copyRandomList(RandomListNode head) {  
     if (head==null) return null;  
     Map<RandomListNode,RandomListNode> map=new HashMap<>();  
     Queue<RandomListNode> qu=new LinkedList<>();  
     RandomListNode x=new RandomListNode(head.label);  
     map.put(head,x);  
     qu.offer(head);  
     while (!qu.isEmpty()) {  
       RandomListNode v=qu.poll();  
       if (v.next!=null && !map.containsKey(v.next)) {  
         RandomListNode w1=new RandomListNode(v.next.label);  
         map.put(v.next,w1);  
         qu.offer(v.next);  
       }  
       if (v.random!=null && !map.containsKey(v.random)) {  
         RandomListNode w2=new RandomListNode(v.random.label);  
         map.put(v.random,w2);  
         qu.offer(v.random);  
       }  
       if (v.next!=null) map.get(v).next=map.get(v.next);  
       if (v.random!=null) map.get(v).random=map.get(v.random);  
     }  
     return map.get(head);  
   }  
 }  

Solution 2: if we know that there is no loop. Code can be much cleaner.

 public class Solution {  
   public RandomListNode copyRandomList(RandomListNode head) {  
     if (head==null) return null;  
     Map<RandomListNode,RandomListNode> map=new HashMap<>();  
     RandomListNode x=head;  
     while (x!=null) {  
       RandomListNode w=new RandomListNode(x.label);  
       map.put(x,w);  
       x=x.next;  
     }  
     x=head;  
     while (x!=null) {  
       map.get(x).next=map.get(x.next);  
       map.get(x).random=map.get(x.random);  
       x=x.next;  
     }  
     return map.get(head);  
   }  
 }