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.

public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) return null;
        HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode dummy = new RandomListNode(-1);
        RandomListNode cursor = dummy;

        // build map between old and new nodes
        RandomListNode p = head;
        while (p != null) {
            // 这里尽量先建立next关系，不要等到后面调用map来建立，会节省不少计算量
            RandomListNode node = new RandomListNode(p.label);
            cursor.next = node;
            cursor = node;

            map.put(p, node);
            p = p.next;
        }

        // build connection
        p = head;
        while (p != null) {
            // 这里建立random关系
            map.get(p).random = map.get(p.random);
            p = p.next;
        }

        return map.get(head);
    }