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.

分析

通过map的key value 来建立原始node和copied node的关系

每次走到一个node，需要check：

1。node本身是否有copy

2。node的next是否有copy

3。node的random是否有copy

当这三者都建立的时候，在建立copy node的两个指针的映射关系

map.get(cur).next = map.get(cur.next);

map.get(cur).random = map.get(cur.random);

/**
 * 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) {
       if(head == null){
           return null;
       }

       Map<RandomListNode,RandomListNode> map = new HashMap<RandomListNode,RandomListNode>();
        RandomListNode cur = head;
       while(head != null){
           if(!map.containsKey(cur)){
               RandomListNode node = new RandomListNode(cur.label);
               map.put(cur,node);
           }
           if(cur.next != null && map.get(cur.next) == null){
                 RandomListNode nextNode = new RandomListNode(cur.next.label);
                map.put(cur.next,nextNode); 
           }
            if(cur.random !=null && map.get(cur.random) == null){
                RandomListNode randomNode = new RandomListNode(cur.random.label);
                map.put(cur.random,randomNode);
            }

           map.get(cur).next = map.get(cur.next);
           map.get(cur).random = map.get(cur.random);


           head = head.next;

       } 

         return map.get(head);


    }
}