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.

复制一个有random pointer的Linked List, 边遍历边构建List Node, 但是这里我们需要用到hashmap，这样保证了对于原来list里的每个node，我们只生成了一个与他对应的新node。
注意null check

public class Solution {
    //Time: O(n)
    public RandomListNode copyRandomList(RandomListNode head) {
        RandomListNode dummy = new RandomListNode(0);
        RandomListNode node = dummy;
        HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
        while (head != null) {
            if (!map.containsKey(head)) {
                map.put(head, new RandomListNode(head.label));
            }
            node.next = map.get(head);
            //null check
            if (head.random != null) {
                if (!map.containsKey(head.random)) {
                    map.put(head.random, new RandomListNode(head.random.label));   
                }
                node.next.random = map.get(head.random);
            }
            head = head.next;
            node = node.next;
        }
        return dummy.next;
    }
}