#138 - Copy List with Random Pointer

MediumLinked List

Construct a deep copy of a linked list where each node has an additional random pointer that can point to any node in the list or null.

Input	Output
head = [[7,null],[13,0],[11,4],[10,2],[1,0]]	[[7,null],[13,0],[11,4],[10,2],[1,0]] (deep copy)
head = [[1,1],[2,1]]	[[1,1],[2,1]] (deep copy)
head = [[3,null],[3,0],[3,null]]	[[3,null],[3,0],[3,null]] (deep copy)

Solution Space

Try it

/**
 * Creates a deep copy of a linked list with random pointers.
 * Uses a hash map to map original nodes to their copies.
 *
 * @param head Head of the original list
 * @returns    Head of the deep-copied list
 */
export function copyRandomList(
  head: NodeWithRandom | null,
): NodeWithRandom | null {
  if (!head) return null;

  // First pass: create a copy of each node, store old→new mapping
  const map = new Map<NodeWithRandom, NodeWithRandom>();
  let curr: NodeWithRandom | null = head;
  while (curr) {
    map.set(curr, new NodeWithRandom(curr.val));
    curr = curr.next;
  }

  // Second pass: wire up next and random pointers on the copies
  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)!;
}

Approach: hash map – first pass clones every node and records an `old → new` mapping; second pass sets `next` and `random` on each clone by looking up the map.

Time: O(n) – two passes through the list.

Space: O(n) – the hash map stores one entry per node.

Alternative approaches:

Approach	Idea	Time	Space
Interleaving (O(1) space)	Weave each copy right after its original (A→A'→B→B'→…), set random via copy.random = original.random.next, then separate the two lists.	O(n)	O(1)

Why the hash-map method is preferred: it is significantly simpler to implement and debug, with the same O(n) time. The O(1)-space interleaving trick is clever but error-prone due to pointer manipulation and mutating the original list temporarily.

#19 Remove Nth Node From End of List

#141 Linked List Cycle