Copy List with Random Pointer

Copy List with Random Pointer is a classic pointer-juggling problem. Each node has an extra random pointer that can point at any node in the list (or None), and you must produce a true deep copy. The elegant solution does it in O(1) extra space with no hash map — by weaving the copies into the original list.

The slow way first

The obvious fix is a hash map: first pass, create a clone of every node and store original -> clone. Second pass, for each original node set clone.next = map[original.next] and clone.random = map[original.random]. That works and is O(n) time — but it costs O(n) extra space for the map.

The question to ask: can I find a node's clone without a separate lookup table? If every clone sat in a known, predictable spot relative to its original, I would not need the map at all.

The idea: weave the clones in

Splice each clone right after its original, so the list becomes 7 -> 7' -> 13 -> 13'. Now the clone of any node X is always X.next — that is the lookup table, built into the list itself. Then clone.random = orig.random.next. Finally, unweave the interleaved chain back into two separate lists.

The key insight: by placing each clone at orig.next, the relationship orig.random.next == clone of orig.random holds for free, so we copy random pointers with no auxiliary storage.

Walk through it

Step through the animation. First the clones (bottom color) get spliced in after each original. Then each clone's random pointer is wired using orig.random.next. Finally the chain is unwoven so the original (top) and the copy (bottom) become two clean, independent lists.

Pseudocode

if list is empty: return None
 
# Pass 1: weave a clone in after each original
cur = head
while cur:
    clone = new node with cur.val
    clone.next = cur.next
    cur.next = clone
    cur = clone.next        # skip past the clone
 
# Pass 2: copy random pointers
cur = head
while cur:
    if cur.random:
        cur.next.random = cur.random.next   # clone's random
    cur = cur.next.next
 
# Pass 3: unweave into original and copy
cur = head
copy_head = head.next
while cur:
    clone = cur.next
    cur.next = clone.next
    clone.next = clone.next.next if clone.next else None
    cur = cur.next
return copy_head

The Python solution

def copy_random_list(head):
    if not head:
        return None
    cur = head
    while cur:
        clone = Node(cur.val)
        clone.next = cur.next
        cur.next = clone
        cur = clone.next
    cur = head
    while cur:
        if cur.random:
            cur.next.random = cur.random.next
        cur = cur.next.next
    cur = head
    copy_head = head.next
    while cur:
        clone = cur.next
        cur.next = clone.next
        clone.next = clone.next.next if clone.next else None
        cur = cur.next
    return copy_head

• Pass 1 (the first while) creates each clone and splices it in right after its original, so the clone of any node X lives at X.next.
• Pass 2 is the heart of the trick: cur.next is the current clone, and cur.random.next is the clone of cur.random. The highlighted line wires the clone's random with no hash map.
• The if cur.random guard handles nodes whose random is None.
• Pass 3 restores each original's next and links the clones together, leaving two independent lists.
• We return copy_head, the head of the deep copy (head.next before unweaving).

Complexity

Both approaches are O(n) time, but the interweave trick drops the extra space from O(n) to O(1) (ignoring the output list, which we must build either way). That space win is exactly what interviewers are fishing for with this problem.

When this pattern shows up

Practice