138. Copy List with Random Pointer

Each node has a next pointer and a random pointer that can point anywhere in the list (or null). Deep-copy the list — a hash map from original to clone lets you resolve every pointer in two linear passes.

● MediumHash MapLinked List TraversalTypeScript

PROBLEM What we're solving

Given a linked list where every node has a val, a next pointer, and a random pointer (which can point to any node in the list or be null), return a fully independent deep copy of the list.

Concrete example: [7→null, 13→0, 11→4, 10→2, 1→0] where each entry is val→random_index. After copying, the new list has the same structure and the same random targets (by position), but no node is shared with the original.

KEY IDEA Map originals to their clones first, wire later

Insight → you can't set clone.random while creating nodes, because the target clone might not exist yet. The fix is to separate creation from wiring: one pass builds a clone for every node and stores original → clone in a map. A second pass wires clone.next and clone.random by looking up each target in the map.

RECIPE Two-pass hash-map algorithm

0 · Edge case. If head is null, return null immediately.
1 · Pass 1 — clone nodes. Walk the original list. For each node, create { val, next: null, random: null } and store it in map.set(original, clone). Skip wiring — you only need shallow copies right now.
2 · Pass 2 — wire pointers. Walk again. For each original node, look up its clone and set clone.next = map.get(cur.next) ?? null and clone.random = map.get(cur.random) ?? null. The map guarantees the targets already exist.
3 · Return. map.get(head)is the new list's head.

Classic confusion → trying to wire randomin a single pass. If node A's randompoints to node C and you haven't cloned C yet, you have nothing to wire to. You must create all clones first, then do the wiring in a second pass (or use the interleave trick below).

COST Complexity & alternatives

Brute force (search by index)

O(n²)

For each random pointer, walk the list to find its index target.

Hash map (two passes)

O(n)

O(n) time; O(n) extra space for the map.

O(1)-space alternative

The interleave trick achieves O(1) extra space. Pass 1: insert each clone immediately after its original (A→A'→B→B'→…). Pass 2: set clone.random = cur.random.next (the interleaved clone). Pass 3: separate the two lists. More code to write; O(n) space is almost always acceptable in interviews.

Pattern transfer →the "create all nodes first, wire later" pattern appears in Clone Graph (BFS/DFS + map), Copy Binary Tree with Random Pointer, and any situation where you deep-copy a structure with cross-references.

RUN IT Clone every node first, wire pointers second

vals =randoms =

step 0 / 17

STARTDeep-copying a 5-node list. Pass 1 will clone every node; Pass 2 will wire the pointers.

1interface Node {
2  val: number;
3  next: Node | null;
4  random: Node | null;
5}
6 
7function copyRandomList(head: Node | null): Node | null {
8  if (!head) return null;
9 
10  // Pass 1: build a clone for every original node.
11▶  const map = new Map<Node, Node>();
12▶  let cur: Node | null = head;
13  while (cur) {
14    map.set(cur, { val: cur.val, next: null, random: null });
15    cur = cur.next;
16  }
17 
18  // Pass 2: wire next and random using the map.
19  cur = head;
20  while (cur) {
21    const clone = map.get(cur)!;
22    clone.next   = cur.next   ? map.get(cur.next)!   : null;
23    clone.random = cur.random ? map.get(cur.random)! : null;
24    cur = cur.next;
25  }
26 
27  return map.get(head)!;
28}

State

pass

null

cur

{}

map

current nodeclone (wired)copy completerandom pointer

slowfast

TYPESCRIPT The solution, annotated

copyRandomList.ts
interface Node {
  val: number;
  next: Node | null;
  random: Node | null;
}

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

  // Pass 1: build a clone for every original node.
  const map = new Map<Node, Node>();
  let cur: Node | null = head;
  while (cur) {
    map.set(cur, { val: cur.val, next: null, random: null });
    cur = cur.next;
  }

  // Pass 2: wire next and random using the map.
  cur = head;
  while (cur) {
    const clone = map.get(cur)!;
    clone.next   = cur.next   ? map.get(cur.next)!   : null;
    clone.random = cur.random ? map.get(cur.random)! : null;
    cur = cur.next;
  }

  return map.get(head)!;
}

Reading it block by block

Lines 11–12 — null guard. An empty list returns null; avoids special-casing the map lookup at the end.

Lines 15–19 — Pass 1: create all clones. Each original node is mapped to a fresh node with the same val and both pointers set to nullfor now. No wiring happens here — we're just building the lookup table so every target exists before we need it.

Lines 22–27 — Pass 2: wire the pointers. For every original cur, look up its clone and set clone.next and clone.random via the map. The optional-chain guard (cur.next ? map.get(cur.next)! : null) handles tail and null random pointers cleanly. The non-null assertion (!) is safe because Pass 1 guarantees every original has a clone.

Line 29 — return the head's clone. map.get(head)! is the entry point into the fully wired copy.

Complexity → O(n) time — two linear passes over n nodes. O(n) space — the hash map stores one entry per node. The O(1)-space interleave approach eliminates the map but requires three passes and more careful pointer surgery.

INTERVIEWFollow-ups they'll ask

"Can you do it in O(1) space?" Yes — interleave clones into the original list (A→A'→B→B'→…), set clone.random = original.random.next, then split the two lists apart.
"What if the list has cycles?"The hash map naturally handles cycles — you'll revisit the same original node and map.get returns the already-created clone instead of looping infinitely.
"How is this different from Clone Graph?" Both use the same original-to-clone map pattern. Graph cloning is typically done with BFS/DFS; list cloning can be done iteratively in two passes since the structure is linear.
"What if random points to a node not yet encountered?" That is exactly why we need two passes. Pass 1 ensures every clone exists before Pass 2 wires any pointer.
"Edge cases?" Empty list (return null), single node with random pointing to itself, all random pointers null.

OPTIMAL Hash Map

copyRandomList.ts
interface Node {
  val: number;
  next: Node | null;
  random: Node | null;
}

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

  // Pass 1: build a clone for every original node.
  const map = new Map<Node, Node>();
  let cur: Node | null = head;
  while (cur) {
    map.set(cur, { val: cur.val, next: null, random: null });
    cur = cur.next;
  }

  // Pass 2: wire next and random using the map.
  cur = head;
  while (cur) {
    const clone = map.get(cur)!;
    clone.next   = cur.next   ? map.get(cur.next)!   : null;
    clone.random = cur.random ? map.get(cur.random)! : null;
    cur = cur.next;
  }

  return map.get(head)!;
}

ALT 1 Brute force — linear-search the original list per random pointer

O(n²) time · O(n) space

Build clones into parallel arrays in one pass, then resolve each next and randomby walking the original list from the head to find the target node's position — a linear scan for every pointer.

approach-2.ts
interface Node {
  val: number;
  next: Node | null;
  random: Node | null;
}

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

  // Collect originals and make a bare clone for each.
  const originals: Node[] = [];
  for (let cur: Node | null = head; cur; cur = cur.next) originals.push(cur);
  const clones: Node[] = originals.map((o) => ({ val: o.val, next: null, random: null }));

  // Helper: position of a node in the original list (linear search).
  const indexOf = (target: Node | null): number =>
    target ? originals.indexOf(target) : -1;

  for (let i = 0; i < originals.length; i++) {
    const ni = indexOf(originals[i].next);
    const ri = indexOf(originals[i].random);
    clones[i].next   = ni === -1 ? null : clones[ni];
    clones[i].random = ri === -1 ? null : clones[ri];
  }

  return clones[0];
}

Note → Each indexOf rescans the list, so resolving all pointers is O(n²). Caching the original to clone correspondence in a Map turns every lookup into O(1), giving the two-pass O(n) optimal.

MNEMONIC The one-liner

"Clone every node first, wire every pointer second — the map is the bridge."

TRIGGERS When you see _ → reach for _

deep-copy a list/graph with cross-references	original→clone hash map
pointer target may not exist yet at assignment time	two-pass: create then wire
O(1) space deep copy of a linked list	interleave clones A→A'→B→B'→…
"clone graph" or "copy with random pointer"	Map + two passes (or BFS/DFS)

SKELETON The reusable shape

skeleton.ts
const map = new Map<Node, Node>();
// Pass 1: clone every node (no wiring yet)
let cur: Node | null = head;
while (cur) {
  map.set(cur, { val: cur.val, next: null, random: null });
  cur = cur.next;
}
// Pass 2: wire next and random
cur = head;
while (cur) {
  const clone = map.get(cur)!;
  clone.next   = cur.next   ? map.get(cur.next)!   : null;
  clone.random = cur.random ? map.get(cur.random)! : null;
  cur = cur.next;
}
return map.get(head)!;

FLASHCARDS Tap to flip

Why can't you wire random in a single pass?

The random target clone might not have been created yet when you need to assign it.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What is the time complexity of the two-pass hash-map solution?

QUESTION 02

Why must you create all clone nodes before wiring any pointers?

QUESTION 03

Trace: list is [7→null, 13→0] (val→random_index). After the algorithm, what is clone[1].random.val?

QUESTION 04

In the O(1)-space interleave approach, how do you set clone.random?

QUESTION 05

What does the map store during Pass 1?

QUESTION 06

If all random pointers are null, what does the algorithm return?

QUESTION 07

Which problem is most structurally similar to Copy List with Random Pointer?

QUESTION 08

#138 · Copy List with Random PointerTwo-pass copy: first create all clones into a hash map keyed by original node, then wire every next and random pointer using the map as a lookup table. O(n) time and O(n) space.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Map originals to their clones first, wire later

RECIPE Two-pass hash-map algorithm

COST Complexity & alternatives

O(1)-space alternative

RUN IT Clone every node first, wire pointers second

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Hash Map

ALT 1 Brute force — linear-search the original list per random pointer

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _