Copy List with Random Pointer

The problem

Each node has val, next, and random (points to any node or null). Return a deep copy of the list.

7 → 13 → 11 → 10 → 1
randoms can point anywhere (including self / null)

next alone is easy; random may point forward or backward, so you can’t clone in one naïve pass without remembering original→copy.

Approach A — Hash map (clear interview default)

1. Walk list; create clone nodes; map original → clone.
2. Second pass: clone.next = map.get(orig.next), same for random.

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

function copyRandomList(head: Node | null): Node | null {
  if (!head) return null;
  const map = new Map<Node, Node>();

  let cur: Node | null = head;
  while (cur) {
    map.set(cur, new Node(cur.val));
    cur = cur.next;
  }

  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)!;
}

Time	O(n)
Space	O(n)

Approach B — Interleave (O(1) extra space)

1. After each original A, insert clone A': A → A' → B → B' …
2. Set A'.random = A.random.next (the clone of random).
3. Unweave into original and copy lists.

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

  // 1. interleave clones
  let cur: Node | null = head;
  while (cur) {
    const copy = new Node(cur.val, cur.next, null);
    cur.next = copy;
    cur = copy.next;
  }

  // 2. random pointers
  cur = head;
  while (cur) {
    if (cur.random) cur.next!.random = cur.random.next;
    cur = cur.next!.next;
  }

  // 3. unweave
  const dummy = new Node(0);
  let copyTail = dummy;
  cur = head;
  while (cur) {
    const copy = cur.next!;
    cur.next = copy.next;
    copyTail.next = copy;
    copyTail = copy;
    cur = cur.next;
  }
  return dummy.next;
}

Time	O(n)
Space	O(1) extra (not counting output)

Interviewers love hearing both; implement map unless they demand O(1) extra.

Edge cases

• Empty list
• Single node, random to self
• random all null
• random forms cycles of references (still fine — not a graph walk of next)

Common mistakes

• Setting random before all clones exist (map approach: two passes)
• Forgetting to restore original list in interleave method
• Shallow copy of node objects

Related to frontend?

Rarely product code — but the identity map while cloning a cyclic structure matches cloning fiber-like graphs or editor document models with cross-refs.

Interview delivery

1. Deep copy next + random.
2. Map first.
3. Optional interleave for O(1) space.
4. Null safety on random.
5. Complexities.

Related

• Clone Graph
• Add Two Numbers Linked List
• Reverse Linked List
• LRU Cache
• JavaScript Interview Guide

Further reading

• LeetCode 138 — Copy List with Random Pointer
• MDN: Map