Marauder Bot

Problem

You are given the head of a linked list where every node has an ordinary next pointer plus an extra random pointer that can point to any other node, or to nothing. Produce a completely independent deep copy: new nodes with the same values, whose next and random pointers mirror the original structure but never point back into it.

Example. A three-node list A -> B -> C where A.random points to C must be copied into a fresh A' -> B' -> C' where A'.random points to C', not to the original C.

Key idea

The difficulty is that a node's random pointer can target a node anywhere in the list, including one not yet created when the copy is built in list order. A naive single pass that sets random immediately runs into targets that do not exist yet.

The fix uses a hash map from each original node to its freshly created copy. In a first pass, walk the original list and create one bare copy node per original, recording the mapping as each is made. In a second pass, walk again and use the map to wire up each copy's next and random: a copy's next is the mapped copy of the original's next, and likewise for random. Because every node was already mapped in the first pass, every lookup in the second succeeds.

Solution

class Node {
  val: number;
  next: Node | null;
  random: Node | null;
  constructor(val = 0, next: Node | null = null, random: Node | null = null) {
    this.val = val;
    this.next = next;
    this.random = random;
  }
}

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

  const oldToNew = new Map<Node, Node>(); // maps each original node to its copy

  let curr: Node | null = head;
  while (curr !== null) {
    oldToNew.set(curr, new Node(curr.val)); // first pass: create bare copies, no links yet
    curr = curr.next;
  }

  curr = head;
  while (curr !== null) {
    const copy = oldToNew.get(curr)!;
    copy.next = curr.next !== null ? oldToNew.get(curr.next)! : null; // second pass: every node is already mapped, so lookups always succeed
    copy.random = curr.random !== null ? oldToNew.get(curr.random)! : null;
    curr = curr.next;
  }

  return oldToNew.get(head)!;
}

Complexity

Time: O(n). Two linear passes over the list.
Space: O(n). The hash map holds one entry per node, in addition to the output copy itself.

Watch out for

A random pointer that is null must map to null in the copy, not be treated as a missing lookup.
The map must be keyed by node identity, not by value, since values can repeat.
Build every copy node before wiring any pointers: wiring during the first pass risks pointing at a copy not yet created.

Pattern

This is the "clone via mapping" pattern: build an old-to-new correspondence first, then rewire all pointers using that lookup. The same idea drives deep-copying any graph-like structure, including Clone Graph.

Copy List with Random Pointer