Copy List with Random Pointer

Examples

Input: A 3-node list with values [1, 2, 3]. random: node0 -> node2, node1 -> node0, node2 -> node1.
Output: A separate copy with values [1, 2, 3] where copy0.random -> copy2, copy1.random -> copy0, copy2.random -> copy1.

Every random link in the copy points at a node inside the copy, mirroring the pattern of the original.

Input: A 2-node list with values [1, 2]. random: node0 -> null, node1 -> node1 (points at itself).
Output: A separate copy with values [1, 2] where copy0.random -> null and copy1.random -> copy1.

Input: head = null (empty list)
Output: null

Constraints

• The number of nodes is between 0 and 1000.

• -10^4 <= Node.val <= 10^4

• random is null or points at a node in the same list.

Approach

The direct approach is to first create a plain copy of every node (with no pointers set yet), and use a hash map to remember which copy corresponds to which original node. Then, in a second pass, use that map to wire up every copy's "next" and "random" pointers by looking up the copies of the original's neighbors. This is simple and correct, but the hash map costs memory proportional to the list's length.

The more elegant approach skips the hash map by temporarily interleaving the copied nodes directly into the original list — each original node gets its copy inserted immediately after it. With that arrangement, "the copy of node X" is always just X.next, so random pointers can be wired up without any lookup structure at all. A final pass then splits the doubled-up list back into the original list and the standalone copy.

Solutions

Brute Force — Hash Map from Original to Copy

First pass: walk the original list and create a bare copy of each node (value only), storing "original node -> copy node" in a map. Second pass: walk the original list again, and for each original node, use the map to set its copy's next and random pointers to the copies of the original's own next and random targets.

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

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

  const copyOf = new Map(); // original node -> its copy

  let curr = head;
  while (curr) {
    copyOf.set(curr, new Node(curr.val));
    curr = curr.next;
  }

  curr = head;
  while (curr) {
    const copy = copyOf.get(curr);
    copy.next = curr.next ? copyOf.get(curr.next) : null;
    copy.random = curr.random ? copyOf.get(curr.random) : null;
    curr = curr.next;
  }

  return copyOf.get(head);
}

Time: O(n) · Space: O(n) — the hash map

Optimal — Interleave Copies In Place

Step 1: for every original node, create its copy and splice it in immediately afterward, so the list temporarily reads original1 -> copy1 -> original2 -> copy2 -> ...

Step 2: now that "the copy of any node X" is always just X.next, walk the interleaved list and set each copy's random pointer to (original's random node).next — which is exactly that random node's copy.

Step 3: walk the interleaved list once more, unhooking the copy nodes from the originals to restore the original list and produce the standalone copied list.

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

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

  // Step 1: interleave a copy after every original node.
  let curr = head;
  while (curr) {
    const copy = new Node(curr.val, curr.next);
    curr.next = copy;
    curr = copy.next;
  }

  // Step 2: wire up random pointers using the interleaving.
  curr = head;
  while (curr) {
    if (curr.random) {
      curr.next.random = curr.random.next;
    }
    curr = curr.next.next;
  }

  // Step 3: split the interleaved list back into two separate lists.
  const dummy = new Node(0);
  let copyCurr = dummy;
  curr = head;
  while (curr) {
    const copy = curr.next;
    curr.next = copy.next; // restore original list's next pointer
    copyCurr.next = copy;
    copyCurr = copy;
    curr = curr.next;
  }

  return dummy.next;
}

Time: O(n) · Space: O(1) extra — aside from the copied nodes themselves