Loading…

mediumLinked ListsLC #138Frequently asked

Copy List with Random Pointer

Q: How do you solve Copy List with Random Pointer using the Hash Map — Old Node → New Node (Optimal for Clarity) approach?

When to use it: Lead with this. It's the cleanest, hardest-to-get-wrong answer and the one most interviewers expect first. We sidestep the forward-reference problem by building all the nodes first and wiring their pointers second. **Why one pass fails.** If you tried to set `clone.random` while creating clones left to right, `original.random` might point to a node further along that you haven't cloned yet — so there's no clone to point at. The fix is to decouple *existence* from *linkage*. **Pass 1 — create every clone.** Walk the original list and, for each node, allocate a new node carrying the same `val`. Record the correspondence in a hash map: `map[original] = clone`. After this pass, every original node has a clone, regardless of where any random pointer leads. **Pass 2 — wire next and random.** Walk the original list again. For each `original`, set `map[original].next = map[original.next]` and `map[original].random = map[original.random]`. Because all clones already exist, every lookup succeeds. Critically, use a *null-safe* lookup (`map.get(...)` returning null for a missing/null key) so that a null `next` or `random` becomes null in the clone instead of throwing. **Why it's fully independent.** Every pointer in the new list is the *result of a map lookup*, so it always resolves to a clone — never to an original node. The original list is read but never mutated. Time complexity: O(n). Space complexity: O(n).

Q: How do you solve Copy List with Random Pointer using the Interleave & Split — O(1) Extra Space approach?

When to use it: Bring this out for the explicit 'can you do it without the hash map?' follow-up. Warn that the unzip step is bug-prone. We eliminate the map by physically placing each clone next to its original, so 'the clone of X' is simply `X.next`. **Pass 1 — interleave.** For each original node, create its clone and splice it directly after: `clone.next = orig.next; orig.next = clone`. The list becomes A → A' → B → B' → C → C'. Now every clone is reachable from its original in one hop. **Pass 2 — assign random pointers.** For each original `orig` (stepping two at a time), the clone is `orig.next`. The clone's random should be the clone of `orig.random`, which — thanks to interleaving — is exactly `orig.random.next`. So `orig.next.random = orig.random.next` (guarding for `orig.random == null`). This is the elegant core: the map lookup became a `.next`. **Pass 3 — unzip.** Now separate the two interleaved lists. Walk through and, for each original, set `orig.next = orig.next.next` (skip the clone) and `clone.next = clone.next.next` (skip the next original) — being careful not to dereference null at the tail. This both extracts the clone list AND **restores the original list** to its initial state, which is required: leaving the lists interleaved silently corrupts the input. **Why it's correct and independent.** Every clone pointer is derived from a clone (`*.next` of an original gives a clone), so no clone references an original after the unzip. The price is the fiddly three-pass pointer surgery — powerful for the space win, but easy to botch under pressure. Time complexity: O(n). Space complexity: O(1).

LCPractice

Linked List · 6 of 24 · 10 min

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand-new nodes, where each new node's value is set to the value of its corresponding original node. Both the next and random pointers of the new nodes should point to new nodes in the copied list such that the pointers in the original and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

Return the head of the copied linked list.

In plain English

We must produce a brand-new list of n nodes whose next and random pointers mirror the original's structure but reference only the new nodes. The challenge is the random pointer: it can point anywhere, including to a node we haven't cloned yet, so we can't just copy as we walk.

Examples

Example 1

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Note: Each pair is [val, random_index]. The clone reproduces values, next order, and random targets using only new nodes.

Example 2

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]
Note: Both nodes' random point to index 1 (the second node); the copy mirrors that with its own nodes.

Example 3

Input: head = []
Output: []
Note: Empty input copies to an empty list — return null.

Constraints

0 ≤ n ≤ 1000
-10⁴ ≤ Node.val ≤ 10⁴
Node.random is null or points to some node in the list
The new list must be completely independent of the original

Clarifying questions4First question: Can the random pointer point to any node, including itself or null?Explore questions

Q1.Can the random pointer point to any node, including itself or null?
Yes — it can target any node in the list, the node itself, or be null. That's why I resolve it through a map rather than computing an offset.
Q2.Must the copy be fully independent of the original?
Completely. No pointer in the new list may reference an original node, and the original must be left intact.
Q3.Is O(n) extra space acceptable, or do you want O(1)?
I'll present the clean O(n) hash-map solution first; if you want the follow-up, the interleave-and-split method achieves O(1) auxiliary space.
Q4.What should I return for an empty list?
Return null. Both approaches guard the empty case naturally.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Deep-copy a list whose nodes each have a next and an arbitrary random pointer. The clean answer maps each original node to its clone in a hash map, then wires up next and random on the clones by looking them up. O(n) time, O(n) space. The follow-up O(1)-space trick interleaves each clone right after its original, sets random from the neighbour, then unzips the two lists.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you handle arbitrary (possibly forward) references by separating 'create all nodes' from 'wire up pointers', and whether you null-safely resolve next/random.

Where candidates slip

Trying to set random in a single pass and dereferencing a clone that doesn't exist yet, or crashing on null random/next instead of mapping null to null.

How to stand out

Lead with the clean two-pass hash map, then offer the O(1)-space interleave-and-split as the follow-up, and stress restoring the original list when unzipping.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Hash Map — Old Node → New Node (Optimal for Clarity)Optimal	`O(n)`	`O(n)`	Lead with this. It's the cleanest, hardest-to-get-wrong answer and the one most interviewers expect first.	Read
2	Interleave & Split — O(1) Extra Space	`O(n)`	`O(1)`	Bring this out for the explicit 'can you do it without the hash map?' follow-up. Warn that the unzip step is bug-prone.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewDeep copy list with random pointersIs O(1) extra space required?NoYesExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Hash Map — Old Node → New Node (Optimal for Clarity)

TimeO(n)SpaceO(n)

Lead with this. It's the cleanest, hardest-to-get-wrong answer and the one most interviewers expect first.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The random pointer can point to a node you haven't copied yet. What if you created every clone first, before touching any pointers?

2Hint 2Explore hint

Pass 1: walk the list and for each original node make a bare clone (just the value), storing original → clone in a hash map.

3Hint 3Explore hint

Pass 2: walk again and for each original set clone.next = map[original.next] and clone.random = map[original.random], using a null-safe lookup so null maps to null.

A · Core idea

We sidestep the forward-reference problem by building all the nodes first and wiring their pointers second.

Why one pass fails. If you tried to set clone.random while creating clones left to right, original.random might point to a node further along that you haven't cloned yet — so there's no clone to point at. The fix is to decouple existence from linkage.

Pass 1 — create every clone. Walk the original list and, for each node, allocate a new node carrying the same val. Record the correspondence in a hash map: map[original] = clone. After this pass, every original node has a clone, regardless of where any random pointer leads.

Pass 2 — wire next and random. Walk the original list again. For each original, set map[original].next = map[original.next] and map[original].random = map[original.random]. Because all clones already exist, every lookup succeeds. Critically, use a null-safe lookup (map.get(...) returning null for a missing/null key) so that a null next or random becomes null in the clone instead of throwing.

Why it's fully independent. Every pointer in the new list is the result of a map lookup, so it always resolves to a clone — never to an original node. The original list is read but never mutated.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

A(random→C) → B(random→A) → C(random→null)

Interactive diagram

The old→new mapping resolves random pointers

pass1 A

Active call / nodeSupporting contextReturned stateNot active

Pass 1 fills the map; pass 2 reads original.random and writes the mapped clone.

Final resultA'(random→C') → B'(random→A') → C'(random→null)

C · Code with teaching comments

solution.javaJava

Hash Map — Old Node → New Node (Optimal for Clarity) — optimal

5 teaching notes

1
/*
2
// Definition for a Node.
3
class Node {
4
    int val;
5
    Node next;
6
    Node random;
7
    public Node(int val) {
8
        this.val = val;
9
        this.next = null;
10
        this.random = null;
11
    }
12
}
13
*/
14
 
15
public Node copyRandomList(Node head) {
16
    if (head == null) return null;
17
    Map<Node, Node> oldToNew = new HashMap<>();
18
    for (Node cur = head; cur != null; cur = cur.next) {
19
        // Pass 1: clone every node by value first, so all clones exist before we wire
20
        // pointers.
21
        oldToNew.put(cur, new Node(cur.val));
22
    }
23
    for (Node cur = head; cur != null; cur = cur.next) {
24
        // Pass 2: fetch the clone of the current original to set its links.
25
        Node clone = oldToNew.get(cur);
26
        // Map the original's next to its clone; get returns null if cur.next is null.
27
        clone.next = oldToNew.get(cur.next);
28
        // Resolve the arbitrary random pointer through the map — works even if it
29
        // points forward.
30
        clone.random = oldToNew.get(cur.random);
31
    }
32
    // The clone of the original head is the new list's head.
33
    return oldToNew.get(head);
34
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.34 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

The map converts 'I need the clone of an arbitrary original node' into an O(1) lookup, which is exactly what arbitrary cross-references demand. This is the identical strategy used to clone a general graph — the random pointer is just one extra edge per node.

ComplexityO(n) time, O(n) space — Two linear passes (create, then wire) → O(n) time. The map holds one entry per node → O(n) space, plus the n new nodes themselves.

E · Edge cases and pitfalls6head = null — Guard returns null immediately; the map is never built.Explore edge cases

Edge cases handled

head = nullGuard returns null immediately; the map is never built.
single node with random → itselfmap has one entry; clone.random = map[node] = the clone itself, correctly self-referential.
all random = nullPass 2 sets every clone.random to null via get(null) → null.

Pitfalls

Indexing the map directly on a null key (map.get(null) is safe, but map[null] in some languages is not).
Trying to set random during a single creation pass — the target clone may not exist yet.
Returning the original head instead of oldToNew.get(head).

03.2

Approach 2 of 2

Interleave & Split — O(1) Extra Space

TimeO(n)SpaceO(1)

Bring this out for the explicit 'can you do it without the hash map?' follow-up. Warn that the unzip step is bug-prone.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Instead of a map to find each clone, what if each clone lived right next to its original so you could reach it via original.next?

2Hint 2Explore hint

Pass 1: insert each clone immediately after its original (A → A' → B → B' → ...). Pass 2: set clone.random = original.random.next, since original.random.next IS the clone of original.random.

3Hint 3Explore hint

Pass 3: unzip the interleaved list back into two — restore the originals' next pointers AND extract the clones' next pointers.

A · Core idea

We eliminate the map by physically placing each clone next to its original, so 'the clone of X' is simply X.next.

Pass 1 — interleave. For each original node, create its clone and splice it directly after: clone.next = orig.next; orig.next = clone. The list becomes A → A' → B → B' → C → C'. Now every clone is reachable from its original in one hop.

Pass 2 — assign random pointers. For each original orig (stepping two at a time), the clone is orig.next. The clone's random should be the clone of orig.random, which — thanks to interleaving — is exactly orig.random.next. So orig.next.random = orig.random.next (guarding for orig.random == null). This is the elegant core: the map lookup became a .next.

Pass 3 — unzip. Now separate the two interleaved lists. Walk through and, for each original, set orig.next = orig.next.next (skip the clone) and clone.next = clone.next.next (skip the next original) — being careful not to dereference null at the tail. This both extracts the clone list AND restores the original list to its initial state, which is required: leaving the lists interleaved silently corrupts the input.

Why it's correct and independent. Every clone pointer is derived from a clone (*.next of an original gives a clone), so no clone references an original after the unzip. The price is the fiddly three-pass pointer surgery — powerful for the space win, but easy to botch under pressure.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

A(random→C) → B(random→A) → C(random→null)

interleave

weave clones in

StateA→A'→B→B'→C→C'

Final resultA'(random→C') → B'(random→A') → C'(random→null)

C · Code with teaching comments

Reference implementation previewpublic Node copyRandomList(Node head) { if (head == null) return null; // Pass 1: interleave clones after originals for (Node cur = head; cur != null; cur = cur.next.next) {Explore the full code

solution.javaJava

Interleave & Split — O(1) Extra Space — reference

4 teaching notes

1
public Node copyRandomList(Node head) {
2
    if (head == null) return null;
3
 
4
    // Pass 1: interleave clones after originals
5
    for (Node cur = head; cur != null; cur = cur.next.next) {
6
        Node clone = new Node(cur.val);
7
        // Splice clone in right after its original so clone == original.next.
8
        clone.next = cur.next;
9
        cur.next = clone;
10
    }
11
 
12
    // Pass 2: assign random pointers on the clones
13
    for (Node cur = head; cur != null; cur = cur.next.next) {
14
        // The clone of cur.random is cur.random.next — the interleaving makes this
15
        // hold; guard for null.
16
        cur.next.random = (cur.random != null) ? cur.random.next : null;
17
    }
18
 
19
    // Pass 3: unzip the two lists
20
    Node dummy = new Node(0);
21
    Node copyTail = dummy;
22
    for (Node cur = head; cur != null; cur = cur.next) {
23
        Node clone = cur.next;
24
        cur.next = clone.next;        // restore original
25
        copyTail.next = clone;        // build copy
26
        copyTail = clone;
27
    }
28
    return dummy.next;
29
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.29 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

Interleaving turns the hash map into adjacency: 'clone of X' becomes 'X.next'. It's a beautiful O(1)-space trick, but the unzip must restore the original list too — forgetting that is the most common way candidates get it marked wrong.

ComplexityO(n) time, O(1) space — Three linear passes (interleave, set random, unzip) → O(n) time. No hash map; only a few pointers are used → O(1) auxiliary space (the n new nodes are required output, not counted).

E · Edge cases and pitfalls6head = null — Guard returns null before any pass runs.Explore edge cases

Edge cases handled

head = nullGuard returns null before any pass runs.
single node, random nullInterleave → A→A'; random null stays null; unzip restores A and returns A'.
random pointing to head from a later nodeResolved via cur.random.next which is head's clone — interleaving handles forward and backward refs alike.

Pitfalls

Forgetting to restore the original list's next in the unzip — corrupts the input.
Dereferencing cur.random.next without the null check on cur.random.
Mismatching the two-step advance and walking off the end of the interleaved list.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code preview/* // Definition for a Node. class Node { int val; Node next;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Resolving random before the clone exists

random can point forward. If you create and fully wire a node in one pass, original.random may have no clone yet, giving null or a crash.

Explore the code comparison

Don't write this

cur = head
while cur:
    clone = Node(cur.val)
    clone.random = old_to_new.get(cur.random)  # cur.random not cloned yet!
    old_to_new[cur] = clone
    cur = cur.next

Write this instead

cur = head
while cur:                       # pass 1: create all clones
    old_to_new[cur] = Node(cur.val)
    cur = cur.next
cur = head
while cur:                       # pass 2: wire pointers
    old_to_new[cur].next = old_to_new.get(cur.next)
    old_to_new[cur].random = old_to_new.get(cur.random)
    cur = cur.next

Not restoring the original list when unzipping

The interleave method mutates the input. If you only extract clones and leave originals pointing at clones, you've corrupted the caller's list.

Explore the code comparison

Don't write this

for (Node cur = head; cur != null; cur = cur.next.next) {
    Node clone = cur.next;
    copyTail.next = clone;
    copyTail = clone;
    // original still points at its clone!
}

Write this instead

for (Node cur = head; cur != null; cur = cur.next) {
    Node clone = cur.next;
    cur.next = clone.next;   // restore original
    copyTail.next = clone;
    copyTail = clone;
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Old→new hash map (or O(1) interleave-and-split)

Code pattern to memorize

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

Rules to remember

1Map original node → clone node; the random pointers force you to resolve nodes you may not have created yet, so build all clones first.
2Use map.get(...) / dict.get(...) so a null next or random maps to null, not a crash.
3Two passes: pass 1 creates every clone, pass 2 wires next and random. One pass can't work because random can point forward.
4For O(1) space, interleave clone after original (A→A'→B→B'…), set clone.random = orig.random.next, then carefully unzip.
5When unzipping, restore the original list's next pointers too — leaving them interleaved is a silent corruption bug.

Use this pattern when

Deep-copy any structure with arbitrary cross-references, not just sequential next pointers
Cloning a graph-like object where you must map originals to copies (Clone Graph is the same idea)
Any time you must resolve references to nodes that may not be constructed yet
Serializing/duplicating linked structures with back- or forward-pointers

Choose another pattern when

There is no random/cross pointer → a plain single-pass copy suffices
You're allowed to share nodes (shallow copy) → no mapping needed
The structure is acyclic and only points backward → you could resolve on the fly without a map

Interview takeaway

An old→new hash map is the universal deep-copy tool for structures with arbitrary pointers — the exact same trick clones graphs. The interleaving method is a neat O(1)-space flex, but the map version is the one to lead with for clarity.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternOld→new hash mapping for deep-copying structures with arbitrary references — the same approach clones graphs and trees-with-random-pointers. The interleave-and-split variant is the niche O(1)-space optimization to reach for only when memory is constrained.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Clone Graph
Coming soon
Same old→new hash map, but each node has a list of neighbours instead of a single random pointer.
Clone Binary Tree With Random Pointer
Coming soon
The tree analogue — map originals to copies, then wire left/right/random.
Add Two Numbers
Different problem, but reinforces building a new list node-by-node with a dummy head.

Same pattern

←

Remove Nth Node From End of List

Continue · Next problem

LRU Cache

mediumLinked ListsLC #138Frequently asked

Copy List with Random Pointer

LCPractice

Linked List · 6 of 24 · 10 min

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Return the head of the copied linked list.

In plain English

Examples

Example 1

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Note: Each pair is [val, random_index]. The clone reproduces values, next order, and random targets using only new nodes.

Example 2

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]
Note: Both nodes' random point to index 1 (the second node); the copy mirrors that with its own nodes.

Example 3

Input: head = []
Output: []
Note: Empty input copies to an empty list — return null.

Constraints

0 ≤ n ≤ 1000
-10⁴ ≤ Node.val ≤ 10⁴
Node.random is null or points to some node in the list
The new list must be completely independent of the original

Clarifying questions4First question: Can the random pointer point to any node, including itself or null?Explore questions

Q1.Can the random pointer point to any node, including itself or null?
Yes — it can target any node in the list, the node itself, or be null. That's why I resolve it through a map rather than computing an offset.
Q2.Must the copy be fully independent of the original?
Completely. No pointer in the new list may reference an original node, and the original must be left intact.
Q3.Is O(n) extra space acceptable, or do you want O(1)?
I'll present the clean O(n) hash-map solution first; if you want the follow-up, the interleave-and-split method achieves O(1) auxiliary space.
Q4.What should I return for an empty list?
Return null. Both approaches guard the empty case naturally.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you handle arbitrary (possibly forward) references by separating 'create all nodes' from 'wire up pointers', and whether you null-safely resolve next/random.

Where candidates slip

Trying to set random in a single pass and dereferencing a clone that doesn't exist yet, or crashing on null random/next instead of mapping null to null.

How to stand out

Lead with the clean two-pass hash map, then offer the O(1)-space interleave-and-split as the follow-up, and stress restoring the original list when unzipping.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Hash Map — Old Node → New Node (Optimal for Clarity)Optimal	`O(n)`	`O(n)`	Lead with this. It's the cleanest, hardest-to-get-wrong answer and the one most interviewers expect first.	Read
2	Interleave & Split — O(1) Extra Space	`O(n)`	`O(1)`	Bring this out for the explicit 'can you do it without the hash map?' follow-up. Warn that the unzip step is bug-prone.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Hash Map — Old Node → New Node (Optimal for Clarity)

TimeO(n)SpaceO(n)

Lead with this. It's the cleanest, hardest-to-get-wrong answer and the one most interviewers expect first.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The random pointer can point to a node you haven't copied yet. What if you created every clone first, before touching any pointers?

2Hint 2Explore hint

Pass 1: walk the list and for each original node make a bare clone (just the value), storing original → clone in a hash map.

3Hint 3Explore hint

Pass 2: walk again and for each original set clone.next = map[original.next] and clone.random = map[original.random], using a null-safe lookup so null maps to null.

A · Core idea

We sidestep the forward-reference problem by building all the nodes first and wiring their pointers second.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

A(random→C) → B(random→A) → C(random→null)

Interactive diagram

The old→new mapping resolves random pointers

pass1 A

Active call / nodeSupporting contextReturned stateNot active

Pass 1 fills the map; pass 2 reads original.random and writes the mapped clone.

Final resultA'(random→C') → B'(random→A') → C'(random→null)

C · Code with teaching comments

solution.javaJava

Hash Map — Old Node → New Node (Optimal for Clarity) — optimal

5 teaching notes

1
/*
2
// Definition for a Node.
3
class Node {
4
    int val;
5
    Node next;
6
    Node random;
7
    public Node(int val) {
8
        this.val = val;
9
        this.next = null;
10
        this.random = null;
11
    }
12
}
13
*/
14
 
15
public Node copyRandomList(Node head) {
16
    if (head == null) return null;
17
    Map<Node, Node> oldToNew = new HashMap<>();
18
    for (Node cur = head; cur != null; cur = cur.next) {
19
        // Pass 1: clone every node by value first, so all clones exist before we wire
20
        // pointers.
21
        oldToNew.put(cur, new Node(cur.val));
22
    }
23
    for (Node cur = head; cur != null; cur = cur.next) {
24
        // Pass 2: fetch the clone of the current original to set its links.
25
        Node clone = oldToNew.get(cur);
26
        // Map the original's next to its clone; get returns null if cur.next is null.
27
        clone.next = oldToNew.get(cur.next);
28
        // Resolve the arbitrary random pointer through the map — works even if it
29
        // points forward.
30
        clone.random = oldToNew.get(cur.random);
31
    }
32
    // The clone of the original head is the new list's head.
33
    return oldToNew.get(head);
34
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.34 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(n) space — Two linear passes (create, then wire) → O(n) time. The map holds one entry per node → O(n) space, plus the n new nodes themselves.

E · Edge cases and pitfalls6head = null — Guard returns null immediately; the map is never built.Explore edge cases

Edge cases handled

head = nullGuard returns null immediately; the map is never built.
single node with random → itselfmap has one entry; clone.random = map[node] = the clone itself, correctly self-referential.
all random = nullPass 2 sets every clone.random to null via get(null) → null.

Pitfalls

Indexing the map directly on a null key (map.get(null) is safe, but map[null] in some languages is not).
Trying to set random during a single creation pass — the target clone may not exist yet.
Returning the original head instead of oldToNew.get(head).

03.2

Approach 2 of 2

Interleave & Split — O(1) Extra Space

TimeO(n)SpaceO(1)

Bring this out for the explicit 'can you do it without the hash map?' follow-up. Warn that the unzip step is bug-prone.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Instead of a map to find each clone, what if each clone lived right next to its original so you could reach it via original.next?

2Hint 2Explore hint

Pass 1: insert each clone immediately after its original (A → A' → B → B' → ...). Pass 2: set clone.random = original.random.next, since original.random.next IS the clone of original.random.

3Hint 3Explore hint

Pass 3: unzip the interleaved list back into two — restore the originals' next pointers AND extract the clones' next pointers.

A · Core idea

We eliminate the map by physically placing each clone next to its original, so 'the clone of X' is simply X.next.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

A(random→C) → B(random→A) → C(random→null)

interleave

weave clones in

StateA→A'→B→B'→C→C'

Final resultA'(random→C') → B'(random→A') → C'(random→null)

C · Code with teaching comments

solution.javaJava

Interleave & Split — O(1) Extra Space — reference

4 teaching notes

1
public Node copyRandomList(Node head) {
2
    if (head == null) return null;
3
 
4
    // Pass 1: interleave clones after originals
5
    for (Node cur = head; cur != null; cur = cur.next.next) {
6
        Node clone = new Node(cur.val);
7
        // Splice clone in right after its original so clone == original.next.
8
        clone.next = cur.next;
9
        cur.next = clone;
10
    }
11
 
12
    // Pass 2: assign random pointers on the clones
13
    for (Node cur = head; cur != null; cur = cur.next.next) {
14
        // The clone of cur.random is cur.random.next — the interleaving makes this
15
        // hold; guard for null.
16
        cur.next.random = (cur.random != null) ? cur.random.next : null;
17
    }
18
 
19
    // Pass 3: unzip the two lists
20
    Node dummy = new Node(0);
21
    Node copyTail = dummy;
22
    for (Node cur = head; cur != null; cur = cur.next) {
23
        Node clone = cur.next;
24
        cur.next = clone.next;        // restore original
25
        copyTail.next = clone;        // build copy
26
        copyTail = clone;
27
    }
28
    return dummy.next;
29
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.29 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6head = null — Guard returns null before any pass runs.Explore edge cases

Edge cases handled

head = nullGuard returns null before any pass runs.
single node, random nullInterleave → A→A'; random null stays null; unzip restores A and returns A'.
random pointing to head from a later nodeResolved via cur.random.next which is head's clone — interleaving handles forward and backward refs alike.

Pitfalls

Forgetting to restore the original list's next in the unzip — corrupts the input.
Dereferencing cur.random.next without the null check on cur.random.
Mismatching the two-step advance and walking off the end of the interleaved list.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code preview/* // Definition for a Node. class Node { int val; Node next;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Resolving random before the clone exists

random can point forward. If you create and fully wire a node in one pass, original.random may have no clone yet, giving null or a crash.

Explore the code comparison

Don't write this

cur = head
while cur:
    clone = Node(cur.val)
    clone.random = old_to_new.get(cur.random)  # cur.random not cloned yet!
    old_to_new[cur] = clone
    cur = cur.next

Write this instead

cur = head
while cur:                       # pass 1: create all clones
    old_to_new[cur] = Node(cur.val)
    cur = cur.next
cur = head
while cur:                       # pass 2: wire pointers
    old_to_new[cur].next = old_to_new.get(cur.next)
    old_to_new[cur].random = old_to_new.get(cur.random)
    cur = cur.next

Not restoring the original list when unzipping

The interleave method mutates the input. If you only extract clones and leave originals pointing at clones, you've corrupted the caller's list.

Explore the code comparison

Don't write this

for (Node cur = head; cur != null; cur = cur.next.next) {
    Node clone = cur.next;
    copyTail.next = clone;
    copyTail = clone;
    // original still points at its clone!
}

Write this instead

for (Node cur = head; cur != null; cur = cur.next) {
    Node clone = cur.next;
    cur.next = clone.next;   // restore original
    copyTail.next = clone;
    copyTail = clone;
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Old→new hash map (or O(1) interleave-and-split)

Code pattern to memorize

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

Rules to remember

1Map original node → clone node; the random pointers force you to resolve nodes you may not have created yet, so build all clones first.
2Use map.get(...) / dict.get(...) so a null next or random maps to null, not a crash.
3Two passes: pass 1 creates every clone, pass 2 wires next and random. One pass can't work because random can point forward.
4For O(1) space, interleave clone after original (A→A'→B→B'…), set clone.random = orig.random.next, then carefully unzip.
5When unzipping, restore the original list's next pointers too — leaving them interleaved is a silent corruption bug.

Use this pattern when

Deep-copy any structure with arbitrary cross-references, not just sequential next pointers
Cloning a graph-like object where you must map originals to copies (Clone Graph is the same idea)
Any time you must resolve references to nodes that may not be constructed yet
Serializing/duplicating linked structures with back- or forward-pointers

Choose another pattern when

There is no random/cross pointer → a plain single-pass copy suffices
You're allowed to share nodes (shallow copy) → no mapping needed
The structure is acyclic and only points backward → you could resolve on the fly without a map

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Clone Graph
Coming soon
Same old→new hash map, but each node has a list of neighbours instead of a single random pointer.
Clone Binary Tree With Random Pointer
Coming soon
The tree analogue — map originals to copies, then wire left/right/random.
Add Two Numbers
Different problem, but reinforces building a new list node-by-node with a dummy head.

Same pattern

←

Remove Nth Node From End of List

Continue · Next problem

LRU Cache