4.9.5 — Copy List with Random Pointer

LeetCode 138 · Medium · ★ Blind 75

The problem

Each node has a next pointer and a random pointer that may point to any node in the list, or to null. Make a deep copy: a completely new set of nodes with the same structure, sharing nothing with the original.

The pattern

Copying next is easy — walk forward and build as you go. The random pointer is the problem: when you are copying node 1 and its random points to node 5, node 5 has not been created yet.

That is the whole difficulty, and it has a name: you need to translate an old node into its new counterpart, before all the counterparts exist.

The fix is to do it in two passes.

1. First pass: create every new node, and record which new node corresponds to each old node.
2. Second pass: now that every counterpart exists, wire up next and random by looking each old pointer up in that record.

The record is a hash map from old node to new node. The nodes themselves are the keys.

The solution

Python

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None

        old_to_new = {}

        # pass 1 — create every node, no pointers yet
        curr = head
        while curr:
            old_to_new[curr] = Node(curr.val)
            curr = curr.next

        # pass 2 — now every counterpart exists, so wire them up
        curr = head
        while curr:
            copy = old_to_new[curr]
            copy.next = old_to_new.get(curr.next)       # .get returns None for null
            copy.random = old_to_new.get(curr.random)
            curr = curr.next

        return old_to_new[head]

TypeScript

function copyRandomList(head: Node | null): Node | null {
  if (!head) return null;

  const map = new Map<Node, Node>();

  let curr: Node | null = head;
  while (curr) {
    map.set(curr, new Node(curr.val));
    curr = curr.next;
  }

  curr = head;
  while (curr) {
    const copy = map.get(curr)!;
    copy.next = curr.next ? map.get(curr.next)! : null;
    copy.random = curr.random ? map.get(curr.random)! : null;
    curr = curr.next;
  }

  return map.get(head)!;
}

old_to_new.get(curr.next) rather than old_to_new[curr.next]. When curr.next is None, the key is not in the map, and [] would raise. .get returns None, which is exactly the value you want to store. One method call replaces two if statements.

Objects as dictionary keys. In Python this works because objects hash by identity by default, which is precisely what you want — two different nodes with the same value must stay different. In JavaScript, Map also compares object keys by identity. Note that this is the opposite of the situation in 4.4.4, where identity comparison was the bug. Here identity is exactly right, because you are tracking specific objects rather than equal values.

Complexity

O(n) time, two passes. O(n) space for the map.

The O(1)-space version

There is a clever solution that removes the map entirely, by storing the correspondence inside the list itself.

Step 1 — weave each copy in behind its original.

A → B → C
becomes
A → A' → B → B' → C → C'

Step 2 — set the random pointers. For any original node curr, its copy is curr.next. And the copy of curr.random is curr.random.next. So:

copy.random = curr.random.next if curr.random else None

The list structure is now doing the job the hash map was doing. That is the whole idea.

Step 3 — unweave, separating the two lists and restoring the original.

class Solution:
    def copyRandomList(self, head):
        if not head:
            return None

        # 1. weave
        curr = head
        while curr:
            curr.next = Node(curr.val, curr.next)
            curr = curr.next.next

        # 2. randoms, using the woven structure as the lookup
        curr = head
        while curr:
            if curr.random:
                curr.next.random = curr.random.next
            curr = curr.next.next

        # 3. unweave
        old, new_head = head, head.next
        while old:
            copy = old.next
            old.next = copy.next
            copy.next = copy.next.next if copy.next else None
            old = old.next

        return new_head

O(n) time, O(1) extra space. It is three passes instead of two, and it temporarily mutates the input, which is a real objection in production code.

Know it, and know when to write it. The map version is the one to lead with — it is clearly correct and easy to explain. Offer this when asked to remove the extra space, and mention the mutation as its cost.

Where this goes next

• Clone Graph (LeetCode 133) — the same problem on a graph rather than a list, so the traversal becomes DFS or BFS and the map does the same job. Chapter 4.20. If you see these two as one problem, you have understood both.
• Deep copy of any object with cycles — a serialiser, structuredClone, or a JSON encoder handling shared references. Every one of them keeps an identity map so a node appearing twice is copied once. Naming this is what turns the problem from a puzzle into general knowledge.

The rule: when a copy must preserve references to objects that may not exist yet, build all the objects first and keep an old-to-new map, then wire the pointers in a second pass.

What the interviewer will push on

"Why can you not do it in one pass?" A random pointer may point forwards to a node not yet created. Naming this before writing anything is the sign you understood the problem.

"What are the keys of your map?" The original nodes themselves, compared by identity. Value-based keys would merge distinct nodes with equal values.

"Can you do it without the map?" The weaving trick. Say the cost: it mutates the input temporarily.

"How does this relate to cloning a graph?" Same problem, different traversal.

One thing to volunteer: say that this is what a deep-copy routine does with shared references. It shows you know the problem is real rather than invented.

Next: 4.9.6 Add Two Numbers — arithmetic on a list, and the carry that must survive past the end.