LeetCode 138 – Copy List with Random Pointer

Copy List with Random Pointer is Clone Graph wearing a linked list's clothes, and it has the same core difficulty: you cannot set a pointer to a node that has not been created yet. The map-based answer is short and obvious. The O(1)-space answer is one of the genuinely clever tricks worth carrying around.

The problem

Each node has a next pointer and a random pointer, which may point at any node in the list or at null. Return a deep copy: the same structure, sharing no node objects with the original.

[[7,null],[13,0],[11,4],[10,2],[1,0]]

  7 -> 13 -> 11 -> 10 -> 1        next pointers
  |     |    |     |     |
 null   7    1     11    7        random pointers

[]           -> []
[[1,1]]      -> a single node whose random points at itself

A node's random can point forwards, which is the whole problem. Copy the list in one forward pass and the first node's random may need to reference a copy that does not exist yet.

The map answer

Exactly the recipe from Clone Graph: a map from original node to its copy, filled before any pointer is set.

pass 1: create every copy, record original -> copy
pass 2: for each node, copy.next   = map[node.next]
                       copy.random = map[node.random]

Separating creation from wiring is what removes the ordering problem entirely — by the time any pointer is assigned, every possible target already exists. map[null] must return null, which a HashMap does for free and a plain Python dict does not, so seed it with None → None or branch.

Java

class Solution {
    public Node copyRandomList(Node head) {
        Map<Node, Node> copies = new HashMap<>();

        // Pass 1: every copy exists before any pointer is set.
        for (Node node = head; node != null; node = node.next) {
            copies.put(node, new Node(node.val));
        }

        // Pass 2: wire them up. get(null) returns null, which is exactly right.
        for (Node node = head; node != null; node = node.next) {
            Node copy = copies.get(node);
            copy.next = copies.get(node.next);
            copy.random = copies.get(node.random);
        }

        return copies.get(head);
    }
}

An empty list returns copies.get(null), which is null. No guard needed.

This is the answer to give first. It is O(n) time and O(n) space, and if the interviewer does not ask for better, it is the right place to stop.

Python

class Solution:
    def copyRandomList(self, head: "Node") -> "Node":
        copies = {None: None}          # so copies[node.random] works when it is None

        node = head
        while node:
            copies[node] = Node(node.val)
            node = node.next

        node = head
        while node:
            copies[node].next = copies[node.next]
            copies[node].random = copies[node.random]
            node = node.next

        return copies[head]

Seeding with {None: None} is the small trick that keeps the second loop branch-free. Without it, copies[node.random] raises a KeyError the moment a random pointer is null — which the very first example has.

The O(1)-space version: interweave, then split

The map exists only to answer "where did this node get copied to?". You can store that answer in the list itself by putting each copy directly after its original:

1. interweave      A -> A' -> B -> B' -> C -> C'

2. set randoms     A'.random = A.random.next
                   because X.next IS X's copy, for every X

3. split           restore A -> B -> C and extract A' -> B' -> C'

Step 2 is the payoff. A.random.next is "the copy of whatever A points at", available in constant time with no lookup, because the interweaving made next mean exactly what the map meant.

    Node copyRandomListInterweaved(Node head) {
        if (head == null) return null;

        // 1. Insert each copy directly after its original.
        for (Node node = head; node != null; node = node.next.next) {
            Node copy = new Node(node.val);
            copy.next = node.next;
            node.next = copy;
        }

        // 2. X.next is X's copy, so X.random.next is the copy X.random should point to.
        for (Node node = head; node != null; node = node.next.next) {
            if (node.random != null) {
                node.next.random = node.random.next;
            }
        }

        // 3. Unweave, restoring the original list as we go.
        Node newHead = head.next;
        for (Node node = head; node != null; node = node.next) {
            Node copy = node.next;
            node.next = copy.next;
            copy.next = (copy.next != null) ? copy.next.next : null;
        }

        return newHead;
    }

The node.random != null guard in step 2 is mandatory — null.next throws. And step 3 must restore the original list, not merely extract the copy: leaving the input mangled is a side effect the caller did not ask for, and interviewers do check.

It is still O(n) time — three passes rather than two — and O(1) auxiliary space, since the only extra memory is the copies themselves, which are the output.

Complexity

Extra space, not total — the output is O(n) either way and does not count.

The pattern

Storing a mapping inside the structure being transformed, rather than beside it, is the reusable idea. It is the same instinct as Flatten Binary Tree's splicing and Morris traversal's threading from problem 94: temporarily abuse pointers you control, then restore them.

The precondition is the same in all three — you must own the structure for the duration and put it back. If anything else could be reading it concurrently, the map is the correct answer and the clever version is a bug.

What the interviewer is checking

• That random pointers can point forwards, which is what breaks a single naive pass.
• Creating every copy before wiring any pointer.
• That null randoms are handled — the map lookup or an explicit guard.
• Empty list, single node, and a node whose random points at itself.
• That the copy shares no nodes with the original.
• That you offer the map version before the clever one.
• If you do the interweaving: that the original list is restored.