Copy List with Random Pointer
Deep-copy a list where each node also has a random pointer to any node (or null).
- 0 <= n <= 1000
- -10⁴ <= Node.val <= 10⁴
- Node.random is null or is pointing to some node in the linked list.
Intuition
To copy list with random pointer you must deep-copy a linked list where each node has the usual next plus a random pointer that can target any node in the list, or null. Copying next is routine. The random pointers are the whole difficulty.
The problem is ordering. Walking the list and copying as you go, you will meet a random pointing at a node whose clone does not exist yet — you cannot wire it up, because there is nothing to wire it to. The obvious fix is a hash map from original node to clone: do one pass to create every clone, a second to wire both pointers through the map. That works and is easy to explain, at O(n) extra space.
The O(1) space solution replaces the map with the list's own structure. Insert each clone immediately after its original, producing A → A' → B → B' → C → C'. Now the map is unnecessary, because the relationship is positional:
- A node's clone is always node.next, so the clone of node.random is node.random.next.
That one identity is the entire trick. Wiring the random pointers becomes a single pass with no lookup structure at all. A third pass then unweaves the two lists, restoring the original exactly as it was — which the problem requires, and which is easy to forget.
The obvious solution is a hash map from original node to clone; the O(1)-space trick is to store that mapping inside the list itself. Weaving each clone directly behind its original means original.next is the lookup table, so random.next finds the cloned target with no dictionary at all. Whenever you need an old-to-new association, ask whether the structure can hold it for you.
Approach
Before reading on: price up what the direct approach costs here, then ask which pointers must be saved before you overwrite anything. Aim for O(n) time and O(1) space.
Understand why a single naive pass fails
When you encounter a random pointer during a straightforward copy, its target's clone may not exist yet. The pointers form arbitrary references, not a traversal order, so no single pass can resolve them without either a lookup structure or the interleaving trick.
Pass one: interleave clones with originals
For each original node, create its clone and splice it in directly after: A → A' → B → B'. Copy only the value at this stage. When the pass finishes, every original is followed immediately by its own clone, which encodes the mapping without a hash map.
Pass two: wire the random pointers
Walk the originals two nodes at a time. For each cur, set cur.next.random = cur.random.next — the clone of cur gets the clone of cur.random. Guard against a null random: cur.random.next would fault, so leave the clone's random as null in that case.
Pass three: unweave the two lists
Separate the interleaved chain back into the original list and the copy by relinking alternating nodes. Restore the originals' next pointers as you go — leaving the input mutated is a correctness failure even though the returned copy would look right.
Compare with the hash map version
A map from original to clone gives the same result in two simpler passes at O(n) extra space. It is the version to write first in an interview; the interleaving is the follow-up when constant extra space is requested. Knowing both, and why the second exists, is what the question is testing.
Cost of the three passes
Each pass visits every node once, so the total is O(n) time with a small constant. Space is O(1) beyond the output itself, since the interleaving replaces the map entirely — that is the whole reason to prefer it.
Solution & live demo
Common pitfalls
Copying the random pointers in the same pass as the clones
while cur:
cur.next = Node(cur.val, cur.next)
cur.next.random = cur.random.next
cur = cur.next.next# pass 1: weave clones # pass 2: wire randoms # pass 3: unweave
A random pointer can target a node further along that hasn't been cloned yet, so cur.random.next is still the original's neighbour rather than its clone. Every clone must exist before any random is wired — that's why the passes can't merge.
Dereferencing a null random
cur.next.random = cur.random.next
if cur.random:
cur.next.random = cur.random.nextRandom is allowed to be null, and None.next raises. A clone's random defaults to null already, so the guard simply skips the assignment.
Not restoring the original list
return head.next
while cur:
clone = cur.next
cur.next = clone.next
clone.next = clone.next.next if clone.next else None
cur = cur.nextLeaving the two lists interleaved means the input is returned corrupted — every original node points at a clone. The third pass separates them, and the trailing null check stops the last clone from dereferencing past the end.
Edge cases
Guard: only assign when cur.random exists.
cur.random.next is the node's own clone — works unchanged.