Copy List with Random Pointer

mediumAmazon-tagged: Mixed30 stepsJava · Python · C++

Deep-copy a list where each node also has a random pointer to any node (or null). First pass: create a copy of every node and map original → copy. Second pass: set each copy's next and random by looking up the originals' targets in the map.

▶ Watch the animated trace

Traced input: head = [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]] → [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]. Original problem: neetcode.io/problems/copy-linked-list-with-random-pointer

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(n)

The interleaving trick brings space to O(1).

Key idea

A random pointer may point forward, so copies must exist before wiring.
The map translates any original node into its copy.
map.get(null) returns null, which handles null pointers for free.

Common mistakes

Pointing a copy's random at the original node.
Trying to wire random pointers in a single pass before their targets exist.

Solution

Java

class RNode {
    int val;
    RNode next, random;
    RNode(int v) { val = v; }
}

RNode copyRandomList(RNode head) {
    Map<RNode, RNode> map = new HashMap<>();
    for (RNode cur = head; cur != null; cur = cur.next) {
        map.put(cur, new RNode(cur.val));
    }
    for (RNode cur = head; cur != null; cur = cur.next) {
        map.get(cur).next = map.get(cur.next);
        map.get(cur).random = map.get(cur.random);
    }
    return map.get(head);
}

Python

class Node:
    def __init__(self, val: int, next: "Node" = None, random: "Node" = None):
        self.val, self.next, self.random = val, next, random


def copyRandomList(head: Optional[Node]) -> Optional[Node]:
    copies = {None: None}
    cur = head
    while cur:
        copies[cur] = Node(cur.val)
        cur = cur.next
    cur = head
    while cur:
        copies[cur].next = copies[cur.next]
        copies[cur].random = copies[cur.random]
        cur = cur.next
    return copies[head]

C++

class Node {
public:
    int val;
    Node *next = nullptr, *random = nullptr;
    Node(int v) : val(v) {}
};

Node* copyRandomList(Node* head) {
    unordered_map<Node*, Node*> copies{{nullptr, nullptr}};
    for (Node* cur = head; cur; cur = cur->next) {
        copies[cur] = new Node(cur->val);
    }
    for (Node* cur = head; cur; cur = cur->next) {
        copies[cur]->next = copies[cur->next];
        copies[cur]->random = copies[cur->random];
    }
    return copies[head];
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Empty list Return null.	`head = []`	`[]`
Random points to itself The copy's random must point to the copy, not the original.	`head = [[1, 0]]`	`[[1, 0]]`
All randoms null Duplicate values are still separate nodes.	`head = [[3, null], [3, null]]`	`[[3, null], [3, null]]`