LeetCode 138 · Medium · Linked List

Copy List with Random Pointer

Each node has a next pointer and a random pointer that can aim at any node or null. Build a deep copy: brand-new nodes whose next and random pointers mirror the original, with no pointer into the old list.

O(n)time · two passes
O(n)space · the map
old → copyhash map

0–7 nodes · val 0 to 99 · random_index is null or a node index

lists row 1 = original · row 2 = copies (′) · solid arrow = next · dashed curve underneath = random

oldToCopy hash map · #i = the node at index i

public Node copyRandomList(Node head) { Map<Node, Node> oldToCopy = new HashMap<>(); oldToCopy.put(null, null); Node cur = head; while (cur != null) { // pass 1: clone every node Node copy = new Node(cur.val); oldToCopy.put(cur, copy); cur = cur.next; } cur = head; while (cur != null) { // pass 2: wire the clones Node copy = oldToCopy.get(cur); copy.next = oldToCopy.get(cur.next); copy.random = oldToCopy.get(cur.random); cur = cur.next; } return oldToCopy.get(head);}
pass
—
cur
—
copy
—
map size
—

Why it works

  1. Brute force fails on random. Copying node by node, a random pointer can aim at a node that has no copy yet, or at one of several nodes with the same value. Looking the target up by walking the list for each node costs O(n²).
  2. The map turns "which copy?" into a lookup. Pass 1 makes every clone and records old → copy. In pass 2 every target, wherever it is, already has a clone, so oldToCopy.get(cur.random) answers in O(1).
  3. Two linear passes: O(n) time. The map holds n + 1 entries: O(n) extra space on top of the copy itself.
  4. Pitfall: null pointers. Seeding the map with oldToCopy.put(null, null) lets cur.next and cur.random be null without an if. A HashMap accepts a null key; a TreeMap or ConcurrentHashMap would throw NullPointerException on it.
  5. Pitfall: never point into the old list. copy.random = cur.random passes a shallow copy on small tests but shares nodes with the input; every pointer must go through the map.
  6. Follow-up, O(1) extra space: weave each clone right after its original (A → A′ → B → B′), set A′.random = A.random.next, then unweave. Clone Graph (133) uses the same old-to-copy map on a graph.