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 Plain-English Breakdown

Imagine you have a linked list of nodes, but it's completely tangled. Not only does each node point to the next one, but it also has a random pointer that can point to literally any node in the list (including itself, or previous nodes, or future nodes). Your job is to create an identical, standalone clone of this entire tangled mess. Modifying the original list is generally frowned upon unless you revert it perfectly.

Constraints to note:

• The list length is between 0 and 1000.
• Node values are integers.
• random can be null.

Brute Force Analysis

A naive approach would be to first copy all nodes using just their next pointers. Then, for every node in the original list, figure out which index its random pointer points to (by starting at the head and counting steps). Finally, take that same number of steps in the cloned list to set the new random pointer.

• Time Cost: Finding the index of a random pointer takes O(N) time per node. Doing this for N nodes takes O(N^2) time.
• Why it fails: While O(N^2) might technically pass for 1000 nodes, it is incredibly inefficient and entirely misses the structural mapping problem the interviewer is looking to test.

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.

ELI5 Analogy: Imagine you are cloning a group of friends who are all holding hands in a line (next), but they are also pointing at their best friend in the group (random). Pass 1: You make a clone of every person and just stand them in a corner. As you make each clone, you write in a notebook: "Original Bob maps to Clone Bob." Pass 2: You look at Original Bob. He is holding hands with Original Alice, and pointing at Original Charlie. You look up your notebook: "Who is Clone Alice? Who is Clone Charlie?" Then you tell Clone Bob to hold hands with Clone Alice and point at Clone Charlie.

Code Walkthrough (Hash Map Approach)

1. Edge Case: If head is null, there is nothing to copy, return null.
2. The Ledger: We create a dictionary old_to_new = {}. This is our notebook.
3. Pass 1 (Creation): We loop through the original list. For each curr node, we create a brand new Node with the same .val. We store this mapping: old_to_new[curr] = Node(curr.val). Notice we are NOT setting .next or .random yet.
4. Pass 2 (Wiring): We reset curr back to the head. We loop through the original list again.
5. Connecting: For the current original node, we fetch its clone: copy = old_to_new[curr]. We then set copy.next to the clone of curr.next (using .get() to safely handle nulls). We set copy.random to the clone of curr.random.
6. Return: Finally, we return the clone of the head node: old_to_new[head].

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.

Derivation:

• Time Complexity: O(N). We walk the list of length N exactly twice. Hash map insertions and lookups take O(1) time on average. Total time is 2N \times O(1) = O(N).
• Space Complexity: O(N). We store every single node from the original list as a key in our hash map, mapped to its copy. This requires N entries in the dictionary. (The space of the copied list itself doesn't count against auxiliary space complexity since it's the required output, but the dictionary does).

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.