Copy List with Random Pointer: when next is not enough

The problem feels deceptively close to a standard linked list copy — iterate, clone each node, wire up next. That would work fine until you hit random. That pointer can aim at any node in the list: the one three positions ahead, the one three positions behind, or the node itself. By the time you are copying node B and trying to set B'.random, the node that B.random points to might not have been cloned yet.

That is the actual problem. How do you set a pointer to a copy that does not exist yet?

The list from Example 1: [[7,null],[13,0],[11,4],[10,2],[1,0]]. Every next edge points right. The random edges scatter freely — node 1 points back to node 0, node 4 points to node 2. A naive single-pass clone breaks the moment it tries to wire random to a node that has not been created yet.

The problem

Given a linked list where each node holds an integer value and two pointers — next to the following node and random to any node in the list (or null) — construct a complete deep copy where no pointer in the new list touches a node in the original. Full statement: LeetCode 138.

Constraints:
- 0 <= n <= 1000
- -10^4 <= Node.val <= 10^4
- Node.random is null or is pointing to some node in the linked list.

What the constraints force

0 <= n <= 1000 and -10^4 <= Node.val <= 10^4.

n up to 1000 means an O(n) algorithm is the only reasonable target. There is no O(n log n) trick to reach for and no O(n^2) brute force that is even tempting at this scale. The constraint is quietly telling you: one or two passes over the list is all you need.

The value range [-10^4, 10^4] is irrelevant to the algorithm. The values are copied as-is; you never sort or search by them. What matters is that you cannot use the values as identity. Two nodes with value 3 are distinct objects — the copy of the first must not secretly point at the copy of the second.

Node.random is either null or points to some node in the same list. It will never escape the list. That guarantee is important: it means every random pointer target already has a position in the list, and you can pre-build all copies before wiring any pointers.

The hardest case structurally: a node whose random points to itself. The algorithm must handle that without blowing up.

Approach 1: hash map — build the copy index first

The cleanest way to solve the back-reference problem is to build all the copies before wiring any pointers. A hash map keyed on original nodes and valued on their clones gives you O(1) lookup when you later need to translate old.random -> new.random.

Two passes: first pass creates all nodes, second pass wires next and random.

class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
 
class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None
 
        old_to_new = {}
 
        # First pass: create all clones, no pointers yet
        current = head
        while current:
            old_to_new[current] = Node(current.val)
            current = current.next
 
        # Second pass: wire next and random using the map
        current = head
        while current:
            clone = old_to_new[current]
            if current.next:
                clone.next = old_to_new[current.next]
            if current.random:
                clone.random = old_to_new[current.random]
            current = current.next
 
        return old_to_new[head]

public class Solution {
    public Node CopyRandomList(Node head) {
        if (head == null) return null;
 
        var oldToNew = new Dictionary<Node, Node>();
 
        // First pass: create all clones
        Node current = head;
        while (current != null) {
            oldToNew[current] = new Node(current.val);
            current = current.next;
        }
 
        // Second pass: wire next and random
        current = head;
        while (current != null) {
            Node clone = oldToNew[current];
            if (current.next != null)
                clone.next = oldToNew[current.next];
            if (current.random != null)
                clone.random = oldToNew[current.random];
            current = current.next;
        }
 
        return oldToNew[head];
    }
}

Hand trace through Example 1

List: 7 -> 13 -> 11 -> 10 -> 1. Let's call the originals A, B, C, D, E.

First pass — after the while loop:

old_to_new = {
    A(7):  A'(7),
    B(13): B'(13),
    C(11): C'(11),
    D(10): D'(10),
    E(1):  E'(1)
}

No next or random pointers set yet. Every clone is an isolated node.

Second pass — wiring, node by node:

current = A(7):
  A'.next   = old_to_new[B] = B'(13)    ✓
  A'.random = null                        ✓

current = B(13):
  B'.next   = old_to_new[C] = C'(11)    ✓
  B'.random = old_to_new[A] = A'(7)     ✓  (random index 0 -> A)

current = C(11):
  C'.next   = old_to_new[D] = D'(10)    ✓
  C'.random = old_to_new[E] = E'(1)     ✓  (random index 4 -> E)

current = D(10):
  D'.next   = old_to_new[E] = E'(1)     ✓
  D'.random = old_to_new[C] = C'(11)    ✓  (random index 2 -> C)

current = E(1):
  E'.next   = null                        ✓
  E'.random = old_to_new[A] = A'(7)     ✓  (random index 0 -> A)

Return old_to_new[head] = A'. The cloned list is fully wired. Not a single original-list node is reachable from the copy.

Complexity: Time O(n) — two traversals, each O(n). Space O(n) — the hash map holds one entry per node.

Approach 2: interweaving — clone in place, O(1) auxiliary space

The hash map works because it stores the mapping from original to clone. But that mapping is only used to answer one question: "given an original node, what is its clone?" The interweaving trick encodes the same answer directly into the list structure, without a separate data structure.

The idea: after cloning node A, insert A' immediately after A in the list. The result is:

A -> A' -> B -> B' -> C -> C' -> null

Now the clone of any node X is simply X.next. That is your O(1) lookup.

Setting random on the clones becomes: clone.random = original.random.next. Because original.random.next is the clone of whatever original.random pointed at.

Three passes total.

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None
 
        # Pass 1: interweave clones into the original list
        current = head
        while current:
            clone = Node(current.val)
            clone.next = current.next
            current.next = clone
            current = clone.next   # jump to the next original node
 
        # Pass 2: set random pointers on clones
        current = head
        while current:
            clone = current.next
            if current.random:
                clone.random = current.random.next
            current = clone.next
 
        # Pass 3: detach the clone list, restore the original
        dummy = Node(0)
        new_cur = dummy
        current = head
 
        while current:
            clone = current.next
            current.next = clone.next   # restore original list
            new_cur.next = clone
            new_cur = clone
            current = current.next
 
        return dummy.next

public class Solution {
    public Node CopyRandomList(Node head) {
        if (head == null) return null;
 
        // Pass 1: interweave clones
        Node current = head;
        while (current != null) {
            Node clone = new Node(current.val);
            clone.next = current.next;
            current.next = clone;
            current = clone.next;
        }
 
        // Pass 2: set random pointers
        current = head;
        while (current != null) {
            Node clone = current.next;
            if (current.random != null)
                clone.random = current.random.next;
            current = clone.next;
        }
 
        // Pass 3: separate the two lists
        Node dummy = new Node(0);
        Node newCur = dummy;
        current = head;
 
        while (current != null) {
            Node clone = current.next;
            current.next = clone.next;
            newCur.next = clone;
            newCur = clone;
            current = current.next;
        }
 
        return dummy.next;
    }
}

Hand trace through Example 2

List: 1 -> 2, with node[0].random = node[1] and node[1].random = node[1] (both random point to node at index 1, which is node 2 with value 2 -- and node 1 also points to itself).

Actually the example is [[1,1],[2,1]]: node 0 (val=1) has random -> index 1, node 1 (val=2) has random -> index 1 (itself).

Pass 1 — interweave:

Start:  1 -> 2 -> null

After cloning node 1(val=1):
  1 -> 1' -> 2 -> null

After cloning node 2(val=2):
  1 -> 1' -> 2 -> 2' -> null

Pass 2 — set random on clones:

current = node 1(val=1):
  clone = node 1'
  current.random = node 2(val=2)
  clone.random   = current.random.next = node 2' ✓

current = node 2(val=2):
  clone = node 2'
  current.random = node 2(val=2) [itself]
  clone.random   = current.random.next = node 2' [itself] ✓

The self-referencing random resolves correctly: node 2'.random points to node 2', not to the original node 2.

Pass 3 — separate:

Extract 1', extract 2'.
Restore original: 1 -> 2 -> null
Clone list:       1' -> 2' -> null

Return 1'.

Complexity: Time O(n) — three passes, each O(n). Space O(1) auxiliary — no hash map, just pointer manipulation. The output list itself is O(n) but that is required by the problem.

Edge cases

Empty list (head = null): Both approaches return null in the first line. Nothing else executes.

Single node, random is null: Pass 1 creates one clone. Pass 2 sees current.random is null, skips. Pass 3 extracts the single clone. Clean.

Single node, random points to itself: The self-referencing case in the trace above. Interweaving handles it: clone.random = current.random.next, and current.random.next is the clone itself. The hash map handles it even more trivially: old_to_new[current.random] = old_to_new[current] = the clone.

All random pointers null: No special handling needed. The if current.random: guards fire false every time.

All nodes have the same value: The value is not used for identity anywhere. The hash map keys on object identity (memory address), not value. The interweaving approach never looks at values for logic. Duplicates are a non-issue.

Random pointer forms a long chain pointing backward: Say node 4 points to node 0, node 3 points to node 0, etc. In the hash map approach, when pass 2 reaches node 4, node 0 and its clone already exist in the map — backward references resolve cleanly because all clones were built in pass 1. In interweaving, backward references work the same way: current.random.next looks at the node right after the original target, which is always its clone after pass 1.

The pattern underneath both approaches

The fundamental problem is forward reference under a non-sequential pointer. You cannot resolve random as you go because it can point to a node you have not seen yet.

Both approaches solve this by separating the problem into phases. You never try to do everything in one pass. First phase: ensure every original node has a corresponding clone in existence. Second phase: wire the pointers, now that all lookup targets are available.

The hash map makes the two-phase structure explicit. The interweaving technique makes it structural — the clone is literally adjacent to its original in memory, so "look up the clone" becomes "take one next step."

This separation pattern shows up in graph cloning problems generally. LeetCode 133 (Clone Graph) uses the same logic: first build nodes for every vertex, then wire edges. The random pointer here is isomorphic to a general graph edge.

Which one to ship

I reach for the hash map version in an interview or production context unless memory is the explicit constraint. The intent is immediately obvious: build the map, then wire the pointers using the map. Two while loops, five lines of logic each. Anyone maintaining this code can understand it in 30 seconds.

The interweaving approach is clever and genuinely O(1) auxiliary space. But it mutates the input list for the duration of the algorithm. If anything goes wrong in pass 2 or 3 — an exception, a bug, a caller assuming the original list is untouched — you have corrupted the input. In a production linked list that lives in shared memory or is accessed concurrently, that is a real hazard. The hash map never touches the original list.

There is also a readability cost: the interweaving technique requires you to remember that "after pass 1, node.next is no longer the next node in the original list — it is the clone." That indirection is non-obvious and needs a comment. The hash map needs no such explanation.

If the interviewer specifically asks for O(1) space, then interweaving is the right answer. Otherwise, I would write the hash map version, explain the trade-off clearly, and note the O(1) alternative.

Comparison

Both are O(n) time. The space difference is the only real trade-off, and whether it matters depends on your memory budget.

Where this sits in the series, and where to go next

The linked list series so far has covered reversal (206), detecting cycles (141), merging sorted lists (21), and reordering lists (143). Those problems manipulate a single pointer structure. LeetCode 138 is the first in the series that forces you to copy a structure — and specifically, to copy one where the reference graph is not a simple chain.

The transferable insight: when you need to deep-copy a structure with non-trivial cross-references, build all the nodes first, then wire the pointers.

Clone Graph (LeetCode 133) is the direct generalization. Instead of a linked list with one random pointer per node, you have an undirected graph where each node can have arbitrarily many neighbors. The hash map approach from Approach 1 above applies almost verbatim — build a map from original to clone, then fill in the neighbor lists. The interweaving trick does not transfer cleanly to general graphs, so the hash map wins there.

Clone Binary Tree With Random Pointer (LeetCode 1485) applies the same random pointer extension to a binary tree. You have left, right, and random. The two-phase structure from Approach 1 — pre-build all clones, then wire — applies directly. The traversal is a tree DFS instead of a linear scan.

Flatten a Multilevel Doubly Linked List (LeetCode 430) is a different flavor: the list has child pointers that create a multi-level structure, and you need to flatten it into a single-level doubly linked list. No deep copy involved, but the pointer manipulation complexity is comparable — you are rewiring a structure that has non-sequential cross-links.

LRU Cache (LeetCode 146) is structurally adjacent: it combines a hash map with a doubly linked list and requires careful pointer wiring on every insertion and deletion. The discipline of tracking which pointers exist and what they should point to — the core skill in LeetCode 138 — is the same skill LRU Cache demands.