Copy List with Random Pointer

Source

LintCode 105

LeetCode 138

Problem

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.

Solution

public RandomListNode copyRandomList(RandomListNode head) {
    Map<RandomListNode, RandomListNode> map = new HashMap();

    RandomListNode copyHead = new RandomListNode(-1);
    RandomListNode copyCur = copyHead;
    RandomListNode cur = head;
    while (cur != null) {
        RandomListNode copyNode;
        if (map.containsKey(cur)) {
            copyNode = map.get(cur);
        } else {
            copyNode = new RandomListNode(cur.label);
        }

        // assign random pointer
        if (map.containsKey(cur.random)) {
            copyNode.random = map.get(cur.random);
        } else if (cur.random == null) {
            copyNode.random = null;
        } else {
            RandomListNode copyRandom = new RandomListNode(cur.random.label);
            copyNode.random = copyRandom;
            map.put(cur.random, copyRandom);
        }
        map.put(cur, copyNode);

        copyCur.next = copyNode;
        copyCur = copyCur.next;
        cur = cur.next;
    }

    return copyHead.next;
}