138. copy list with random pointer

 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class  {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }

        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode dummy = new RandomListNode(0);
        RandomListNode prev = dummy;
        while (head != null) {
            RandomListNode newNode;
            if (map.containsKey(head)) {
                newNode = map.get(head);

            } else {
                newNode = new RandomListNode(head.label);
                map.put(head, newNode); // we add the real node to the map, even if head point to diff nodes, it won't change.!!!!
            }

            RandomListNode oldRandom = head.random;
            if (oldRandom != null) {
                RandomListNode newRandom;
                if (map.containsKey(oldRandom)){
                    newRandom = map.get(head.random);
                } else {
                    newRandom = new RandomListNode(oldRandom.label);
                    map.put(oldRandom, newRandom);
                }            
                newNode.random = newRandom;
            }



            prev.next = newNode;
            prev = newNode; // prev 赋给新node！！！
            head = head.next;

        }
        return dummy.next;

    }
}