LeetCode #138 Medium

Copy List with Random Pointer

Deep-copy a list where each node also has a random pointer to any node (or null).

linked-listhash-table

02

Intuition

The hard part is wiring random in the copy — the target may not exist yet when you meet the pointer. Interleave copies with originals (A→A'→B→B'…): then every original's random copy is exactly random.next, no map needed.

How to spot this pattern

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.

03

Approach

1

Pass 1 — interleave

After each original node insert its clone: A→A'→B→B'. Clones are reachable from their originals in O(1).

2

Pass 2 — wire randoms

For each original cur, its clone's random is cur.random.next (the clone of cur.random). Nulls pass through.

3

Pass 3 — unweave

Split the interleaved list back into original and copy, restoring the original intact.

04

Solution & live demo

▶1class Solution:
▶2    def copyRandomList(self, head):
▶3        if not head: return None
▶4        cur = head                      # 1) interleave clones
▶5        while cur:
▶6            nxt = cur.next
▶7            cur.next = Node(cur.val, nxt)
▶8            cur = nxt
▶9        cur = head                      # 2) wire randoms
▶10        while cur:
▶11            if cur.random:
▶12                cur.next.random = cur.random.next
▶13            cur = cur.next.next
▶14        cur, copy_head = head, head.next
▶15        while cur:                      # 3) unweave
▶16            clone = cur.next
▶17            cur.next = clone.next
▶18            clone.next = clone.next.next if clone.next else None
▶19            cur = cur.next
▶20        return copy_head

05

Common pitfalls

Copying the random pointers in the same pass as the clones

✗ Wrong

while cur:
    cur.next = Node(cur.val, cur.next)
    cur.next.random = cur.random.next
    cur = cur.next.next

✓ Right

# 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

✗ Wrong

cur.next.random = cur.random.next

✓ Right

if cur.random:
    cur.next.random = cur.random.next

Random 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

✗ Wrong

return head.next

✓ Right

while cur:
    clone = cur.next
    cur.next = clone.next
    clone.next = clone.next.next if clone.next else None
    cur = cur.next

Leaving 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.

06

Edge cases

random is null

Guard: only assign when cur.random exists.

random points to itself

cur.random.next is the node's own clone — works unchanged.

07

Complexity

Time

O(n)

Space

O(1)

Three passes; no hash map thanks to interleaving.