Clone a List with Random Pointers

Before we start

A normal linked list clone is trivial — walk and copy. The challenge here is the random pointer, which can point to any node, including nodes you haven't created yet. This forces you to think about the order in which you create and wire nodes. By the end you will be able to:

• Explain why a hashmap naturally solves the forward-reference problem.
• Write the O(1)-space interleave solution — the approach interviewers love — from memory in three clean passes.
• Trace both solutions on a 4-node example.

Picture this first (no code yet)

The actual problem

Copy List with Random Pointer (LC #138):

Each node has val: int, next: Node | None, and random: Node | None. random can point to any node in the list or None. Return a deep copy — a completely new list where no node is shared with the original.

Example:

Original:
  1 → 2 → 3 → 4 → None
  random: 1→3, 2→1, 3→4, 4→2

After cloning, every node must be a new object; cloned random pointers point to cloned nodes, not originals.

First, the slow way (so you feel the pain)

Naive approach: walk the list, create a copy of each node with only val set. Keep the copies in an array. Walk again: for each original node, look up its random in the array using its index. This requires O(n) space for the array and O(n) time per random lookup (to find the index of the random target). Total: O(n²) time. Unacceptable for a list of 10,000 nodes — 10⁸ operations.

The turning point

The one idea to remember

Approach 1: Hashmap (two-pass)

def copyRandomList(head):
    if not head:
        return None

    old_to_new = {}   # maps original node → its clone

    # Pass 1: create all clone nodes
    cur = head
    while cur:
        old_to_new[cur] = Node(cur.val)
        cur = cur.next

    # Pass 2: wire next and random pointers
    cur = head
    while cur:
        clone           = old_to_new[cur]
        clone.next      = old_to_new.get(cur.next)    # None if cur.next is None
        clone.random    = old_to_new.get(cur.random)  # None if cur.random is None
        cur = cur.next

    return old_to_new[head]

Line-by-line narration:

1. old_to_new = {} — dictionary: keys are original node objects (by identity, not value), values are their clones.
2. Pass 1 — create every clone with only val set; no pointers yet.
3. Pass 2 — for each original, its clone already exists for every node, so old_to_new[cur.next] and old_to_new[cur.random] are both safe to look up (they exist). .get() returns None when the key is None, which is the correct behaviour.
4. return old_to_new[head] — the clone of the original head.

Complexity: O(n) time (two passes), O(n) space (hashmap with n entries).

Approach 2: Interleave (O(1) space, three passes)

def copyRandomList(head):
    if not head:
        return None

    # Pass 1: interleave clones between originals
    # Original: A → B → C
    # After:    A → A' → B → B' → C → C'
    cur = head
    while cur:
        clone     = Node(cur.val)
        clone.next = cur.next
        cur.next  = clone
        cur       = clone.next   # advance to next original

    # Pass 2: set random pointers of clones
    # clone_of(X) = X.next
    # clone_of(X.random) = X.random.next
    cur = head
    while cur:
        if cur.random:
            cur.next.random = cur.random.next
        cur = cur.next.next   # skip the clone, go to next original

    # Pass 3: restore original list and extract clone list
    old_head = head
    new_head = head.next
    cur = head
    while cur:
        clone      = cur.next
        cur.next   = clone.next            # restore original's next
        clone.next = clone.next.next if clone.next else None  # wire clone's next
        cur        = cur.next              # advance to next original
    return new_head

Pass 1 narration: Insert each clone directly after its original. The clone captures the original's old next as its own next. The original's next is updated to point to the clone.

Pass 2 narration: cur.next is the clone of cur. cur.random.next is the clone of cur.random. So cur.next.random = cur.random.next sets the clone's random to the clone of the original's random — with O(1) lookup using the interleaved structure.

Pass 3 narration: Disentangle the two interleaved lists by resetting each original's next to skip over the clone, and each clone's next to skip over the next original.

Watch it happen, frame by frame

List: 1 → 2 → 3, random: 1→3, 2→1, 3→None

After Pass 1 (interleave):

1 → 1' → 2 → 2' → 3 → 3' → None

Node pointers: 1.next=1', 1'.next=2, 2.next=2', 2'.next=3, 3.next=3', 3'.next=None.

Pass 2 (set randoms):

cur=1: random=3, 3.next=3'. So 1'.random = 3'. ✅
cur=2: random=1, 1.next=1'. So 2'.random = 1'. ✅
cur=3: random=None → skip.

Pass 3 (separate):

cur=1:
  clone=1', cur.next = 1'.next = 2 (original restored)
  clone.next = 2.next = 2' (clone chain wired)
  cur = cur.next = 2

cur=2:
  clone=2', cur.next = 2'.next = 3
  clone.next = 3.next = 3'
  cur = 3

cur=3:
  clone=3', cur.next = 3'.next = None
  clone.next = None (clone.next is None → guarded)
  cur = None

Original restored: 1 → 2 → 3 → None
Clone:             1'→ 2'→ 3'→ None  with randoms 1'→3', 2'→1', 3'→None ✅

Which approach to use?

Start with Approach 1 if you're asked in a time-pressured setting. Offer Approach 2 as a follow-up when the interviewer asks "can you do it with O(1) space?"

Common traps

d = {}
cur = head
while cur: d[cur] = Node(cur.val); cur = cur.next
cur = head
while cur:
    d[cur].next   = d.get(cur.next)
    d[cur].random = d.get(cur.random)
    cur = cur.next
return d[head]

Pass 1: insert clone after each original.
Pass 2: cur.next.random = cur.random.next  (if cur.random).
Pass 3: separate originals and clones, fix next pointers.

Check yourself

Practice problems

Chapter 4 complete!

You have now covered all ten Linked List patterns:

Next chapter: Stacks & Queues — monotonic stacks, deque sliding window, and more.