Copy List Random Pointer | Deep Copy | Linked List

Overview

Copy list with random pointer means deep-copying a linked list where each node has val, next, and random (a pointer to any node in the list or null). You must create new nodes so that the copy's structure and random references match the original. Two common approaches: (1) Hash map: one pass to create a copy of each node (map old → new), second pass to set next and random from the map. O(n) time, O(n) space. (2) In-place interleaving: create a copy of each node and insert it right after the original; then set each copy's random to original.random.next; finally unweave the two lists. O(n) time, O(1) extra space (excluding the new list).

Key idea: The hard part is linking the copy's random to the correct copy. A map gives O(1) lookup from old node to new node. The in-place method uses the fact that the copy of node X is always at X.next, so copy.random = original.random.next (when random is non-null).

When to Use

Deep copy a list with random pointers — Exact problem.
Clone a graph — Same idea: map old node → new node, then set neighbors.

How It Works

Map approach:

First pass: for each node, create a new node with the same val; store map.set(oldNode, newNode).
Second pass: for each old node, set newNode.next = map.get(oldNode.next) ?? null, newNode.random = map.get(oldNode.random) ?? null.
Return map.get(head).

In-place (interweave):

For each node, create a copy and insert it after the node (copy.next = node.next, node.next = copy).
For each original node (step by 2 or use the original list): copy.random = original.random ? original.random.next : null.
Unweave: separate the list of originals and the list of copies by rewiring next pointers. Return the head of the copy list.

Example 1: Copy with Hash Map

Problem: A linked list of length n has nodes with val, next, and random. Return a deep copy of the list.

function copyRandomList(head: Node | null): Node | null {
  if (head === null) return null;
  const map = new Map<Node, Node>();
  let curr: Node | null = head;
  while (curr !== null) {
    map.set(curr, new Node(curr.val));
    curr = curr.next;
  }
  curr = head;
  while (curr !== null) {
    const copy = map.get(curr)!;
    copy.next = curr.next !== null ? map.get(curr.next)! : null;
    copy.random = curr.random !== null ? map.get(curr.random)! : null;
    curr = curr.next;
  }
  return map.get(head)!;
}

Time: O(n), Space: O(n).

Example 2: Copy with O(1) Space (Interweave)

Problem: Same; use O(1) extra space (the new list doesn't count).

function copyRandomList(head: Node | null): Node | null {
  if (head === null) return null;
  let curr: Node | null = head;
  while (curr !== null) {
    const copy = new Node(curr.val);
    copy.next = curr.next;
    curr.next = copy;
    curr = copy.next;
  }
  curr = head;
  while (curr !== null) {
    if (curr.random !== null) (curr.next as Node).random = curr.random.next;
    curr = (curr.next as Node).next;
  }
  const dummy = new Node(-1);
  let tail = dummy;
  curr = head;
  while (curr !== null) {
    tail.next = curr.next as Node;
    tail = tail.next;
    curr.next = (curr.next as Node).next;
    curr = curr.next;
  }
  return dummy.next;
}

Time: O(n), Space: O(1) extra.

Edge Cases

Empty list — Return null.
Single node, random = null — One copy; random is null.
Single node, random = self — Copy's random should point to the copy itself.
Random forms a cycle — Map and interweave both work; no infinite loop if you iterate by structure (next), not by random.

Common Mistakes

Not handling null random — Check random !== null before mapping or before setting copy.random = original.random.next.
Losing the list during unweave — In the interweave method, advance curr using the saved next (e.g. curr.next = copy.next) so you don't lose the rest of the original list.
Map key — Use the node object as key (reference), not node.val; multiple nodes can have the same val.

Time and Space Complexity

Time: O(n) for both approaches.
Space: O(n) for map; O(1) extra for interweave (output list excluded).

Summary

Copy list with random: Map old → new, then set next and random; or interweave copies, set random via original.random.next, then unweave.
Same pattern applies to cloning graphs. No direct link to other linked-list concepts; uses basic traversal and pointers.

Copy List with Random Pointer