Copy List with Random Pointer

LINKED LIST · MEDIUM

Builds on Day 15: Linked Lists

This problem adds a second pointer type (random) on top of the standard next pointer; read that lesson first if walking and rewiring a linked list’s pointers is still a new idea.

The problem

You’re given the head of a linked list where every node has two pointers instead of one: the usual next, which walks straight through the list (or is null at the end), and a second pointer called random, which can point to any node anywhere in the list — including the node itself, or null. Your job is to build a complete, independent deep copy of the whole list: every new node must have its own next and random pointing to the corresponding new nodes, never back to any node from the original list.

For example, a list represented as [val, randomIndex] pairs — [[7,null],[13,0],[11,1]] — describes three nodes: node 0 has value 7 and a null random pointer; node 1 has value 13 and its random points at node 0; node 2 has value 11 and its random points at node 1. The copy must reproduce that exact same shape — same values in the same order, same random-target relationships — using entirely new node objects. Getting the values right but pointing any next or random pointer back at an original node (instead of its copy) is an incorrect solution, even if it “looks” right when printed.

LeetCode: Copy List with Random Pointer

Solution 1: Hash map, two passes

The natural first idea: since random can point anywhere, you need some way to translate “an original node” into “its corresponding copy node” — and a Map keyed by the original node objects themselves is exactly that translation table. Pass 1 walks the original list once, creating a copy of every node (with next/random left unset) and recording original → copy in the map. Pass 2 walks the original list again, and for every node, looks up the map to wire its copy’s next and random to the copies of whatever the original pointed to.

Two passes are required, not one — a node’s random can point forward to a node that hasn’t been copied yet. If wiring happened during the same pass as creation, that lookup could miss (the copy simply wouldn’t exist in the map yet). Splitting into “create everything first, then wire everything” sidesteps that ordering problem entirely.

[[7,null],[13,0],[11,1]] — node 1's random points at node 0; node 2's random points at node 1

Press Play or Step to begin.

Step 0 / 0

▶ Play⏭ Step↺ Reset

The code

function copyRandomListHashMap(head) {
  if (!head) return null;
  const copyMap = new Map();

  // Pass 1: create a copy of every original node. next/random are left
  // unset for now — some randoms point forward to nodes not copied yet.
  let cur = head;
  while (cur) {
    copyMap.set(cur, { val: cur.val, next: null, random: null });
    cur = cur.next;
  }

  // Pass 2: wire next/random using the map to translate original -> copy.
  cur = head;
  while (cur) {
    const copy = copyMap.get(cur);
    copy.next = cur.next ? copyMap.get(cur.next) : null;
    copy.random = cur.random ? copyMap.get(cur.random) : null;
    cur = cur.next;
  }

  return copyMap.get(head);
}

Line by line:

• copyMap is a real Map, keyed by the original node objects themselves (not their values) — that reference-identity keying is exactly what lets pass 2 translate “this original node” into “its copy” reliably, even when several nodes share the same val.
• Pass 1 only ever reads cur.next to advance — it never touches random, so the order nodes get copied in is guaranteed to be the same order as the original list, and every original node is guaranteed to have an entry in the map before pass 2 starts.
• copy.next = cur.next ? copyMap.get(cur.next) : null; — translates the original’s next pointer into the copy’s next pointer via one map lookup. Same pattern for random on the next line.
• return copyMap.get(head); — the map already has every original-to-copy mapping, so the copy of the head is just one more lookup away.

Complexity

Time	Space	Approach
O(n)	O(n)	Hash map translating original nodes to copy nodes, two linear passes

Solution 2: Optimal — interleaving, O(1) extra space

The hash map’s whole job is answering one question over and over: “given this original node, where’s its copy?” The interleaving trick answers that question without a map at all, by exploiting a structural guarantee it builds itself: splice every copy node in immediately after its original, so the list becomes A → A' → B → B' → C → C' → .... Once that’s true, the copy of any node is always just one .next hop away from the original — copyOf(X) === X.next, always, by construction. No lookup structure needed; the list’s own shape is the lookup table.

Pass 1 — interleave. Walk the original list once. For each node, create its copy and insert it right after: the original’s next is reassigned to point at the new copy, and the copy’s next takes over whatever the original used to point to.

Pass 2 — wire random. Walk the (now interleaved) list again, stepping by the original nodes only. For each original node A, its copy’s random pointer is A.next.random = A.random ? A.random.next : null — take one more hop off A.random to land on its copy. This is only correct because pass 1 guarantees “one hop past any node is that node’s copy” for every node in the list, including whatever A.random points to.

Pass 3 — separate. Walk the interleaved list one final time and split it back into two independent lists: each original’s next is restored to skip over its copy (pointing at the next original), and each copy’s next is set to skip over the next original (pointing at the next copy). No array, no map — the whole algorithm uses a constant number of pointer variables no matter how long the list is.

[[7,null],[13,0],[11,1]] — same example, watch the list become interleaved then split back apart

Press Play or Step to begin.

Step 0 / 0

▶ Play⏭ Step↺ Reset

The code

function copyRandomListInterleave(head) {
  if (!head) return null;

  // Pass 1: interleave a copy of every node right after the original.
  let cur = head;
  while (cur) {
    const copy = { val: cur.val, next: cur.next, random: null };
    cur.next = copy;
    cur = copy.next;
  }

  // Pass 2: wire each copy's random pointer. The copy of any node X is
  // always X.next (thanks to pass 1) — so the copy of original.random
  // is exactly original.random.next.
  cur = head;
  while (cur) {
    const copy = cur.next;
    copy.random = cur.random ? cur.random.next : null;
    cur = copy.next;
  }

  // Pass 3: separate the interleaved list back into two independent lists.
  cur = head;
  const newHead = head.next;
  while (cur) {
    const copy = cur.next;
    cur.next = copy.next;
    copy.next = copy.next ? copy.next.next : null;
    cur = cur.next;
  }

  return newHead;
}

Line by line:

• Pass 1’s const copy = { val: cur.val, next: cur.next, random: null }; cur.next = copy; is the entire splice: the copy’s next takes over what the original used to point to, then the original’s next is reassigned to the copy. cur = copy.next advances past the copy to the next original.
• Pass 2’s copy.random = cur.random ? cur.random.next : null; is the key trick in one line — cur.random is some original node (or null), and one more .next off of it lands on that node’s copy, because pass 1 guarantees every original is immediately followed by its own copy.
• Pass 3’s cur.next = copy.next; restores the original list — it now points to the next original, skipping the copy sitting between them. copy.next = copy.next ? copy.next.next : null; does the mirror image for the copy list, skipping the next original to reach the next copy.
• const newHead = head.next; is captured before pass 3’s loop runs — it’s the copy of the head, which is exactly what pass 1 spliced in right after head, and it stays correct throughout pass 3 since that line never touches head.next again until the loop reassigns it on its very first iteration.

Complexity

Time	Space	Approach
O(n)	O(1)	Interleaving trick — three linear passes, no auxiliary map

Complexity comparison

Solution	Time	Space
Hash map (two passes)	O(n)	O(n)
Optimal (interleaving)	O(n)	O(1)

Both solutions are O(n) time — the interleaving solution runs three linear passes instead of two, so it is not asymptotically (or even practically) faster, and it would be dishonest to claim it is. The real, honest improvement is space: the Map that grows to hold one entry per node is replaced entirely by the list’s own structure, dropping extra space from O(n) down to O(1).

Interview corner

Q: Why does interleaving a copy right after every original guarantee that “the copy of node X is always X.next”? What would break if pass 1 inserted copies in a different order, or in a separate pass from creation?

• It’s guaranteed because pass 1 processes nodes in list order and, for each one, immediately does two things back to back: create the copy, then splice it in as that exact node’s next. There’s no gap in which a node exists without its copy sitting directly after it.
• If copies were created in one pass and spliced in during a later, separate pass, pass 2’s random-wiring trick (original.random.next) couldn’t be trusted — some nodes would have copies that exist but aren’t in position yet, so “one hop past X” would not reliably mean “X’s copy” at the moment pass 2 needs it to.
• This is also exactly why pass 1 reassigns cur.next to the copy before advancing — the moment a node is processed, its copy is already “live” in the list structure, which is what pass 2 depends on for every single node, not just some of them.

Q: Solution 1 does two separate passes — could you merge pass 1 and pass 2 into a single loop that creates each node’s copy and wires its random pointer at the same time?

• No — a node’s random can point forward to a node that hasn’t been copied yet in the single pass. In the traced example, if node 0 processes first and its random happened to point at node 2, copyMap.get(node2) would come back undefined, because node 2’s copy doesn’t exist yet.
• Splitting into “create every copy first” (pass 1) then “wire every pointer” (pass 2) sidesteps the ordering problem completely — by the time pass 2 runs a single lookup, every original node, no matter where it sits in the list, already has an entry in the map.
• The interleaving solution has a similar-looking constraint and handles it the same way: pass 2 (wiring random) only starts after pass 1 (creating and splicing every copy) has fully finished, for exactly the same forward-pointer reason.

Q: What is the actual, honest complexity improvement of the interleaving solution over the hash-map solution — and what would be dishonest to claim?

• Both solutions are O(n) TIME. The interleaving solution runs three linear passes instead of two, so it isn’t asymptotically faster — claiming a time win would be incorrect.
• The real difference is SPACE: the hash map is O(n) because it holds one entry per node, while the interleaving solution is O(1) — a constant number of pointer variables, regardless of how long the list is.
• The honest framing is “same time complexity, different technique, real space win” — not “brute force vs. optimal” in the Big-O sense. The hash map is a completely legitimate, commonly-used solution; the interleaving trick just trades a small amount of extra bookkeeping complexity for dropping the auxiliary memory entirely.
• ↳ Common follow-up: “Which would you actually use in production code?” The hash-map version, almost always — it’s easier to read, easier to get right under interview pressure, and O(n) space for a linked list copy is rarely the bottleneck. The interleaving trick is the kind of thing worth knowing exists (and demonstrating you can derive), not necessarily the default choice.

Q: Trick question — Solution 1 keys a Map by the original node objects themselves, not by an index or a value. Would a plain JavaScript object ({}) work as a drop-in replacement for that Map?

const a = { val: 7 };
const b = { val: 13 };
const obj = {};
obj[a] = 'copy-of-a';
obj[b] = 'copy-of-b';
console.log(Object.keys(obj).length); // ?
console.log(obj[a]);                  // ?

• Answer: 1, then 'copy-of-b' — not two separate entries.
• Plain object property keys are always coerced to strings. Every plain object stringifies to the exact same value, "[object Object]" — so obj[a] and obj[b] are actually the same key, and setting obj[b] silently overwrites whatever obj[a] held.
• Map keys use the object’s real reference identity, not a stringified form — so copyMap.set(a, ...) and copyMap.set(b, ...) are always distinct entries, no matter how similar (or identical) the objects’ own properties look.
• ⚠ Trap: for this exact problem, a plain object wouldn’t just be slower — it would be silently wrong. Every original node would collide onto the same "[object Object]" key, so copyMap.get(cur) in pass 2 would return whichever copy was created last, for every single node — wiring every copy’s next/random to the same wrong node instead of its actual counterpart. This only surfaces with node-object keys; a plain object is perfectly fine for keys that are already meant to be strings or numbers.

Quiz

Quiz: 1. Why does Solution 1 need two separate passes instead of creating and wiring each copy in one loop?

A random pointer can point forward to a node that hasn’t been copied yet in a single combined pass

A node’s random pointer can point forward to a node that hasn’t been copied yet in a single combined pass — copyMap.get() on that not-yet-created node would return undefined. Two passes guarantee every original has a copy in the map before any wiring is attempted.

Quiz: 2. What is the real, honest complexity improvement of the interleaving solution over the hash-map solution?

Space only — both are O(n) time, but extra space drops from O(n) to O(1)

Both solutions are O(n) time — the interleaving solution actually runs three passes instead of two, so it isn’t asymptotically faster. The real, honest improvement is space: O(n) for the Map down to O(1) for a constant number of pointer variables.

Quiz: 3. In the optimal solution, why is the copy of any node X always exactly X.next after pass 1?

Because pass 1 splices each copy in immediately after its original, one node at a time

Because pass 1 splices each copy in immediately after its original, one node at a time — the moment a node is processed, its copy is already living right at X.next.

Quiz: 4. What does pass 3 (the final pass) of the optimal solution actually do?

Separates the interleaved list back into two independent lists by restoring each list’s own next pointers

Separates the interleaved list back into two independent lists by restoring each list’s own next pointers.

Quiz: 5. Why can’t a plain JavaScript object ({}) safely replace the Map in Solution 1, when the keys are node objects?

Plain object keys are coerced to strings, and every object stringifies to the same “[object Object]” — all node keys would collide

Plain object keys are coerced to strings, and every object stringifies to the same “[object Object]” — all node keys would collide onto the same entry, silently wiring every copy to the same wrong node.