Coding Interview: Copy a Linked List with Random Pointers

Prompt and Applicable Context

Given the head of an acyclic singly linked list, each node contains val, next, and random. The random pointer is either null or refers to any node reachable through the list's next chain, including the node itself. Return a deep copy with exactly one new node for each original node. If original node x points to original node y through either field, the copy of x must point through that field to the copy of y.

Node values are not unique, so value cannot identify a node. The next chain is finite, although random edges may point backward, forward, or form cycles. The returned list must share no nodes with the input, and the input must have its original structure when the function returns.

This is a data-structure and object-identity problem. The baseline answer uses a map from each original object to its copy. A follow-up can require constant auxiliary space; that version temporarily interleaves copies with originals and then restores the input. Output nodes do not count as auxiliary space, but they still consume O(n) total memory.

What the Interviewer Evaluates

The first signal is whether the candidate defines deep copy structurally. Equal values are insufficient. The answer needs a one-to-one mapping f from original nodes to new nodes such that both relationships are preserved: the copy of x.next is f(x).next, and the copy of x.random is f(x).random.

The second signal is handling a reference before its target has been copied. A one-pass value copy cannot safely wire a forward random edge. The straightforward solution separates allocation from wiring: create every destination node first, then connect pointers through the identity map.

The third signal is deriving the space optimization rather than reciting it. After placing each copy immediately after its original, the copy of any original node r is exactly r.next. That local invariant replaces the map during random-pointer assignment.

Finally, the interviewer looks for mutation discipline. The interleaving method is incomplete until it restores every original next pointer, extracts a valid copied chain, and explains when temporarily mutating the input is unacceptable.

Questions to Clarify Before Answering

• Can random point outside the list? This prompt says no. If external nodes belong to the clone, the scope becomes a general reachable-graph copy; if they do not, the output contract must say whether to retain, clear, or reject those references.
• Can the next chain contain a cycle? No. If it can, a loop that follows only next never terminates without a visited set, and the problem is better treated as graph cloning.
• May the algorithm mutate the input temporarily? The map solution does not. The interleaving solution does and is appropriate only when the function has exclusive mutable access and restores the list before returning.
• What counts as extra space? The copied nodes are required output. The map costs O(n) auxiliary space; interleaving uses O(1) auxiliary pointers in addition to the O(n) output.
• Are values unique? No. A map keyed by value merges distinct nodes and corrupts references; keys must be node identities.
• What should empty input return? Return null.

30-Second Answer Framework

“I will first solve it with an original-to-copy identity map. One pass allocates every copied node, and a second pass assigns copied next and random pointers by looking up the corresponding original targets. That is O(n) time and O(n) auxiliary space. If the interviewer requires constant auxiliary space and temporary mutation is allowed, I can insert each copy immediately after its original. Then an original random target's copy is its next node. A third pass separates the chains while restoring the input. Both methods are linear; the interleaving version uses O(1) auxiliary space, excluding the required output.”

Step-by-Step Deep Answer

A shallow copy fails because it reuses original references. Copying only values also fails: two different nodes may have the same value, and random can point to a node that has not yet appeared in the traversal. Following random recursively is not a shortcut because random edges may form cycles.

The safest baseline creates a bijection explicitly. The first pass allocates one new object per original. The second pass translates both outgoing edges through that map. Including null -> null in the lookup is optional; explicit null checks are usually clearer in an interview.

class RandomListNode {
  val: number
  next: RandomListNode | null
  random: RandomListNode | null

  constructor(
    val: number,
    next: RandomListNode | null = null,
    random: RandomListNode | null = null,
  ) {
    this.val = val
    this.next = next
    this.random = random
  }
}

function copyWithMap(head: RandomListNode | null): RandomListNode | null {
  if (head === null) return null

  const copies = new Map<RandomListNode, RandomListNode>()

  let current: RandomListNode | null = head
  while (current !== null) {
    copies.set(current, new RandomListNode(current.val))
    current = current.next
  }

  current = head
  while (current !== null) {
    const copy = copies.get(current)!
    copy.next = current.next === null ? null : copies.get(current.next)!
    copy.random = current.random === null ? null : copies.get(current.random)!
    current = current.next
  }

  return copies.get(head)!
}

The invariant after the first pass is simple: every original visited through next has exactly one distinct entry in the map, and no copied pointer has to target an unallocated node. During the second pass, translating an edge from x to y into an edge from f(x) to f(y) preserves the graph. The method takes two linear passes, so time is O(n) and auxiliary space is O(n).

To remove the map, store the same correspondence temporarily in the list topology. Transform this chain:

A -> B -> C -> null

into this interleaved chain:

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

Now A' is A.next, and if A.random points to C, then the correct target for A'.random is A.random.next, which is C'. This works for forward edges, backward edges, self-references, and repeated targets because it depends on object position, not values.

function copyByInterleaving(head: RandomListNode | null): RandomListNode | null {
  if (head === null) return null

  let current: RandomListNode | null = head
  while (current !== null) {
    const copy: RandomListNode = new RandomListNode(current.val, current.next)
    current.next = copy
    current = copy.next
  }

  current = head
  while (current !== null) {
    const copy: RandomListNode = current.next!
    copy.random = current.random === null ? null : current.random.next
    current = copy.next
  }

  const copiedHead = head.next
  current = head

  while (current !== null) {
    const copy: RandomListNode = current.next!
    const nextOriginal: RandomListNode | null = copy.next

    current.next = nextOriginal
    copy.next = nextOriginal === null ? null : nextOriginal.next
    current = nextOriginal
  }

  return copiedHead
}

Correctness follows from three pass invariants. After pass one, each original is immediately followed by its unique copy. During pass two, every copied random edge goes to the copy immediately after the original target. During pass three, each iteration restores one original edge and connects one copied edge to the next copied node. When the loop ends, the original chain is restored and every pointer reachable from the copied head targets only copied nodes.

The interleaving method performs three linear passes, so time remains O(n). It stores only a fixed number of working pointers, so auxiliary space is O(1), excluding the required n new nodes. It is not automatically the better production choice: during the first two passes, other readers see a corrupted-looking input, and an exception before separation can leave the list interleaved. The map solution is easier to audit and supports immutable or shared input.

Test structure, identity, and restoration separately. Cover an empty list; one node with random = null; one node whose random points to itself; duplicate values; two nodes whose random pointers cross; forward and backward random edges; and many nodes pointing to the same target. After cloning, mutate a copied value and verify the original is unchanged. Traverse the original again to verify its next chain was restored, and assert that no copied next or random pointer belongs to the original-node set.

High-Quality Sample Answer

“The important part is preserving node identity, not just values. Values may repeat, and a random edge can point forward or form a cycle, so I would not key anything by value or recursively follow random pointers without visited state.

My baseline is two passes with an identity map. The first pass walks the acyclic next chain and allocates one copy per original. The second pass translates both pointers through the map. That directly establishes a one-to-one correspondence, takes linear time, and uses linear auxiliary space. It is the version I would choose when the input is immutable, shared, or the simplest auditable implementation matters.

If constant auxiliary space is a hard requirement and I may mutate temporarily, I would insert each copy after its original. That makes the mapping implicit: the copy of any original target is target.next. I then assign every copied random pointer and unzip the alternating chain. The unzip pass must update both chains, so the original is exactly restored and the copy contains no references back into it.

I would prove the three invariants after weaving, random assignment, and separation, then test self-random, duplicate values, crossed random edges, empty input, and post-copy independence. Both versions are O(n) time; the second is O(1) auxiliary space but still allocates O(n) output and is unsafe with concurrent readers.”

Common Mistakes

• Key the map by node value -> duplicate values collapse distinct identities -> key by the original node object.
• Copy random directly -> the output still points into the input -> translate every non-null target to its copied node.
• Allocate and wire in one naive forward pass -> a forward random target may not exist yet -> allocate all nodes first or create missing copies through a complete identity map.
• Follow random pointers recursively without visited state -> random cycles cause infinite recursion or duplicate nodes -> use the finite next chain for this contract or a visited map for general graphs.
• Call the interleaving method O(1) space without qualification -> the returned list still contains n new nodes -> say O(1) auxiliary space excluding required output.
• Assign copy.random = current.random.next without a null check -> a null random pointer crashes -> preserve null explicitly.
• Detach only the copied chain -> original nodes remain linked through copies -> restore the original and build the copied chain in the same separation pass.
• Use interleaving on shared input -> concurrent readers observe inserted copies -> use the map solution unless exclusive temporary mutation is guaranteed.
• Test values only -> a shallow copy can pass value comparisons -> assert distinct identities, translated edges, original restoration, and mutation independence.

Follow-Up Questions and Responses

Follow-up 1: What if the input must never be modified, even temporarily?

Use the identity-map solution. It gives O(n) time and O(n) auxiliary space while leaving the source untouched throughout execution. Copying into arrays by traversal index also consumes O(n) space and still needs an identity-to-index mapping unless the input already exposes stable indices. The interleaving optimization violates the stronger immutability contract even if it later restores the list.

Follow-up 2: What if random can point to a node outside the next chain?

First define clone ownership. If external nodes must also be copied, the input is a graph whose outgoing edges are next and random; use DFS or BFS with an identity map and clone every reachable node once. If external nodes are intentionally shared, the contract must permit retained external references. Interleaving cannot discover or position copies for arbitrary external targets.

Follow-up 3: What if the next pointers can form a cycle?

A plain while current !== null traversal will not terminate. Treat both fields as graph edges and keep a visited identity map. Create a node's copy the first time it is discovered, then enqueue unseen neighbors. Time and space become O(V + E) for the reachable graph, with at most two outgoing edges per node in this model.

Follow-up 4: How would you verify that the copy is truly deep?

Build a map only in the test from original identities to copied identities while walking both next chains. Assert equal lengths and values, different node identities, and for each edge that the copied target equals the mapped original target. Also assert that no output pointer is in the original-node set. Finally mutate values and pointers in the copy and confirm the source is unchanged; for interleaving, compare the source's pre-call and post-call pointer identities.

Follow-up 5: Which solution would you ship?

Default to the two-pass map version because its invariant is explicit and it never exposes a transiently modified input. Choose interleaving only when auxiliary memory is a measured constraint, the list is exclusively owned for the whole call, and failure handling can guarantee restoration. The asymptotic space improvement does not erase concurrency, exception-safety, and maintainability costs.