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.

Tips:

注意用hashmap找映射，next和random都一定要映射到新点上。

Code:

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