Module 11 · Linked Lists and Pointer Mutation

110. Copy List with Random Pointer

Interview · Download this solution · All solutions and shared helpers

Problem

Deep-copy a finite acyclic next-chain whose nodes also have random links to any node in that same chain or None. Return a new head with identical values and next/random relationships, sharing no nodes with the original. Original links must remain unchanged.

Examples

Example 1

head=build_list([1,2]); head.random=head.next; head.next.random=head; clone=copy_random_list(head)
(clone.val, clone.next.val, clone.random is clone.next, clone.next.random is clone, clone is not head)
=> (1, 2, True, True, True)

The clone preserves both cross-links using fresh identities.

Example 2

copy_random_list(None)
=> None

An empty chain has an empty copy.

Example 3

head=build_list([7]); head.random=head; clone=copy_random_list(head)
(clone is not head, clone.random is clone)
=> (True, True)

A self-random link must point to the clone itself.

Reveal the worked solution and reasoning

Why this mechanism works

Values are not unique identifiers, so map original node identities to clone identities. First allocate every clone; only then wire links. This separation ensures that forward random references already have destinations when they are connected.

State and boundaries

clones maps each original node to exactly one fresh node. After allocation, every legal next or random target has a mapped clone.

Protocol

Walk next links and allocate one clone per original node.
Walk the chain again.
Set clone.next from the next-node mapping.
Set clone.random from the random-node mapping.
Return the mapped head.

Visualization

original A.next=B, A.random=B, B.random=A
map A->A', B->B'
clone A'.next=B', A'.random=B', B'.random=A'

Python implementation

from structures import ListNode, build_list

def copy_random_list(head):
    clones = {}
    current = head
    while current is not None:
        clones[current] = ListNode(current.val)
        current = current.next
    current = head
    while current is not None:
        clones[current].next = clones.get(current.next)
        clones[current].random = clones.get(current.random)
        current = current.next
    return clones.get(head)

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

(clone.val, clone.next.val, clone.random is clone.next, clone.next.random is clone, clone is not head)

L4 copy_random_list: clones = {}
head=N1(val=1,next=N2,random=N2); clones={}

L5 copy_random_list: current = head
head=N1(val=1,next=N2,random=N2); clones={}; current=N1(val=1,next=N2,random=N2)

L7 copy_random_list: clones[current] = ListNode(current.val)
head=N1(val=1,next=N2,random=N2); clones={N1(val=1,next=N2,random=N2):N3(val=1,next=None,random=None)}; current=N1(val=1,next=N2,random=N2)

L8 copy_random_list: current = current.next
head=N1(val=1,next=N2,random=N2); clones={N1(val=1,next=N2,random=N2):N3(val=1,next=None,random=None)}; current=N2(val=2,next=None,random=N1)

L7 copy_random_list: clones[current] = ListNode(current.val)
head=N1(val=1,next=N2,random=N2); clones={N1(val=1,next=N2,random=N2):N3(val=1,next=None,random=None), N2(val=2,next=None,random=N1):...; current=N2(val=2,next=None,random=N1)

L8 copy_random_list: current = current.next
head=N1(val=1,next=N2,random=N2); clones={N1(val=1,next=N2,random=N2):N3(val=1,next=None,random=None), N2(val=2,next=None,random=N1):...; current=None

L9 copy_random_list: current = head
head=N1(val=1,next=N2,random=N2); clones={N1(val=1,next=N2,random=N2):N3(val=1,next=None,random=None), N2(val=2,next=None,random=N1):...; current=N1(val=1,next=N2,random=N2)

L11 copy_random_list: clones[current].next = clones.get(current.next)
head=N1(val=1,next=N2,random=N2); clones={N1(val=1,next=N2,random=N2):N3(val=1,next=N4,random=None), N2(val=2,next=None,random=N1):N4...; current=N1(val=1,next=N2,random=N2)

L12 copy_random_list: clones[current].random = clones.get(current.random)
head=N1(val=1,next=N2,random=N2); clones={N1(val=1,next=N2,random=N2):N3(val=1,next=N4,random=N4), N2(val=2,next=None,random=N1):N4(v...; current=N1(val=1,next=N2,random=N2)

L13 copy_random_list: current = current.next
head=N1(val=1,next=N2,random=N2); clones={N1(val=1,next=N2,random=N2):N3(val=1,next=N4,random=N4), N2(val=2,next=None,random=N1):N4(v...; current=N2(val=2,next=None,random=N1)

L13 copy_random_list: current = current.next
head=N1(val=1,next=N2,random=N2); clones={N1(val=1,next=N2,random=N2):N3(val=1,next=N4,random=N4), N2(val=2,next=None,random=N1):N4(v...; current=None

Result: (1, 2, True, True, True). The clone preserves both cross-links using fresh identities.

copy_random_list(None)

L4 copy_random_list: clones = {}
head=None; clones={}

L5 copy_random_list: current = head
head=None; clones={}; current=None

Result: None. An empty chain has an empty copy.

Why the solution is correct

The first pass creates a bijection between reachable original and fresh nodes. The second pass maps each edge through that bijection, preserving structure and aliasing patterns without sharing identities. Since no original field is assigned, the source remains unchanged.

Time and space

O(n) expected time and O(n) mapping space plus O(n) returned nodes.

Common mistakes

Mapping by value merges distinct equal-valued nodes. Copying a random pointer directly leaves the clone linked into the original structure.

Reasoning card

State: clones maps each original node to exactly one fresh node. After allocation, every legal next or random target has a mapped clone.

Invariant: Every copied pointer targets a copied node or None.

Decision to rehearse: Map originals to copies, then wire references; or interleave copies.

Finish: Return the mapped head

Transfer exercise

Explore the interleaving-clones method that removes the dictionary, and explain how the original next links must be restored.