DSA-058 · Three-pass interleaving as an implicit identity map

Copy List with Random Pointer

Advanced · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 18960 deterministic checks. Learner drafts are not executed.

Understand the problem

Deep-copy a singly linked list whose nodes have both next and random references. Preserve values and both edge relations in fresh nodes, and restore the original list after the optimized interleaving algorithm.

head is null or roots a finite acyclic next chain of at most 100,000 nodes. Every random is null or points to a node in that same next chain; random edges may be forward, backward, self-referential, or shared. Values are arbitrary final ints.
Return null for null input; otherwise return a fresh next chain in the same order. Each original node has exactly one distinct copy with equal value, and both next/random targets translate to their corresponding copies. No copied edge may point into the original graph.
The optimized method requires exclusive permission to temporarily rewrite original next links. Every original next and random is restored/preserved on normal completion. The map baseline performs no input writes. Cyclic next chains, external random targets, and concurrent observation/mutation are outside this contract.
Interleaving does not provide strong exception safety if allocation fails during pass one: an OutOfMemoryError may leave a partially woven source. Use the read-only map baseline when temporary mutation or this failure behavior is unacceptable. The algorithm does not catch resource exhaustion or claim rollback.

Examples

Input: N0(7)→N1(7)→N2(9); random=[N2,N1,N2]
Output: Fresh C0→C1→C2; random=[C2,C1,C2]
Duplicate values remain distinct identities. Two edges share C2, and C1 retains its self-random relation.
Input: N0.next=null, N0.random=N0
Output: C0.next=null, C0.random=C0
A self-loop through random is legal; a next self-loop is outside the contract.
Input: null
Output: null
No nodes allocated and no writes.

Before you start

Node identity and graph isomorphism
Saved successors while changing links
Temporary mutation and restoration contracts

Recognize the structure

This is graph copying with a distinguished acyclic next spine. A map translates each original identity into its copy. If temporary writes are allowed, placing a copy immediately after each original makes original.next serve as that translation, removing the auxiliary map.

Try before revealing

Hint 1

How would an original-to-copy identity map translate a random edge?

Hint 2

Can the copy be placed somewhere reachable directly from its original without a map?

Hint 3

Weave copies, translate random through target.next, then unweave both chains while restoring the source.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Explicit original-to-copy identity map

Pass one traverses next and allocates one copy per original into an IdentityHashMap. Pass two translates each original next and random through that map. For N0.random=N2, the copied random becomes map.get(N2), never N2 itself. Forward references work because all copies exist before edge wiring. Expected O(n) time, O(n) map space plus O(n) output; original fields are never changed.

Improve the baseline

Weave one copy after each original

For each current original, allocate copied with the same value, preserve current.next in copied.next, set current.next=copied, and advance to the saved original successor. The chain becomes N0→C0→N1→C1→….

Translate random only after all copies exist

For each original, its copy is current.next. If current.random is nonnull, the corresponding copied target is current.random.next because the entire spine has already been woven. Set copied.random accordingly and advance by two next edges.

Separate and restore in one pass

Save result=head.next. For each original, copied=current.next and nextOriginal=copied.next. Restore current.next=nextOriginal, then set copied.next to nextOriginal.next (its still-woven copy) or null. Advance to nextOriginal; no random fields in the source were ever written.

Why it is correct

Pass-one bijection

After each insertion, every processed original has one unique adjacent copy, with equal value and its old successor stored after that copy. Advancing via copied.next skips the new node. At completion each original has exactly one copy, even if values repeat.

Pass-two edge translation

All original targets are within the spine by precondition, so for a target T, T.next is its unique copy throughout pass two. Therefore each copied random edge preserves null, self-target, backward/forward, and shared-target relations without pointing to an original.

Pass-three restoration and independence

Before processing an original, its own pair and all later pairs remain woven; earlier originals and copies are already separated. Restoring current.next uses the saved original successor. nextOriginal.next still names that successor’s copy, so copied.next is wired correctly before the next iteration. At termination all original next edges are restored, random edges untouched, and every copied edge targets a copy or null.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.IdentityHashMap;

public final class Solution {
    public static final class Node {
        public final int value;
        public Node next;
        public Node random;
        public Node(int value) { this.value = value; }
    }

    public static Node copy(Node head) {
        if (head == null) return null;
        Node current = head;
        while (current != null) {
            Node copied = new Node(current.value);
            copied.next = current.next;
            current.next = copied;
            current = copied.next;
        }
        for (current = head; current != null; current = current.next.next)
            current.next.random = current.random == null ? null : current.random.next;
        Node result = head.next;
        current = head;
        while (current != null) {
            Node copied = current.next;
            Node nextOriginal = copied.next;
            current.next = nextOriginal;
            copied.next = nextOriginal == null ? null : nextOriginal.next;
            current = nextOriginal;
        }
        return result;
    }

    public static Node baseline(Node head) {
        IdentityHashMap<Node, Node> copies = new IdentityHashMap<>();
        for (Node p = head; p != null; p = p.next) copies.put(p, new Node(p.value));
        for (Node p = head; p != null; p = p.next) {
            Node copied = copies.get(p);
            copied.next = copies.get(p.next);
            copied.random = copies.get(p.random);
        }
        return copies.get(head);
    }
}

Read the meaningful blocks

Allocate before publishing each pair

A new node is initialized before current.next is redirected. This local ordering protects the successor but does not provide whole-operation rollback if a later allocation fails.

Finish weaving before random translation

An unprocessed forward target has no adjacent copy yet. Combining the first two passes would miswire a forward random edge.

Restore original before advancing

The saved nextOriginal is essential: after copied.next changes, it points to a copy, not the next original. Advance via the saved original reference.

Complexity

For n nodes, three optimized passes take O(n) time and O(1) auxiliary references excluding the O(n) returned copy nodes. The woven copies are the output, not an extra hidden n-node work buffer.

The identity-map baseline takes O(n) expected time with O(n) additional mapping storage plus O(n) output allocation. It is the appropriate alternative for a read-only or concurrently observed source; interleaving’s constant workspace comes with temporary mutation and weaker failure guarantees.

Exact-state walkthroughs

Reveal normal and boundary traces

Forward, self, and shared random targets

Input: {"values":[7,7,9],"random":[2,1,2]} · Copied graph view: [{"id":"C0","value":7,"next":"C1","random":"C2"},{"id":"C1","value":7,"next":"C2","random":"C1"},{"id":"C2","value":9,"next":null,"random":"C2"}]

Step 1 of 11: Begin with only original identities.

Original random targets all belong to the acyclic next spine or are null.

Deep copy — original and copied graph edges

Phase: initial. current: N0

N0: 7next → N1random → N2current
N1: 7next → N2random → N1
N2: 9next → nullrandom → N2

Cards remain in identity order; follow the named links for traversal order. N nodes are originals and C nodes are new copies. Intermediate next links are woven; the last pass restores originals and separates the copies.

State after this step
Variable	Value
nodes	`[{"id":"N0","value":7,"next":"N1","random":"N2"},{"id":"N1","value":7,"next":"N2","random":"N1"},{"id":"N2","value":9,"next":null,"random":"N2"}]`
pointers	`{"current":"N0"}`
phase	`"initial"`

See the affected Java block

 1 import java.util.IdentityHashMap;
 2 
 3 public final class Solution {
 4     public static final class Node {
 5         public final int value;
 6         public Node next;
 7         public Node random;
 8         public Node(int value) { this.value = value; }
 9     }
10 
11     public static Node copy(Node head) {
12         if (head == null) return null;
13         Node current = head;
14         while (current != null) {
15             Node copied = new Node(current.value);
16             copied.next = current.next;
17             current.next = copied;
18             current = copied.next;
19         }
20         for (current = head; current != null; current = current.next.next)
21             current.next.random = current.random == null ? null : current.random.next;
22         Node result = head.next;
23         current = head;
24         while (current != null) {
25             Node copied = current.next;
26             Node nextOriginal = copied.next;
27             current.next = nextOriginal;
28             copied.next = nextOriginal == null ? null : nextOriginal.next;
29             current = nextOriginal;
30         }
31         return result;
32     }
33 
34     public static Node baseline(Node head) {
35         IdentityHashMap<Node, Node> copies = new IdentityHashMap<>();
36         for (Node p = head; p != null; p = p.next) copies.put(p, new Node(p.value));
37         for (Node p = head; p != null; p = p.next) {
38             Node copied = copies.get(p);
39             copied.next = copies.get(p.next);
40             copied.random = copies.get(p.random);
41         }
42         return copies.get(head);
43     }
44 }
45

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Begin with only original identities.
Original random targets all belong to the acyclic next spine or are null.
nodes
[{"id":"N0","value":7,"next":"N1","random":"N2"},{"id":"N1","value":7,"next":"N2","random":"N1"},{"id":"N2","value":9,"next":null,"random":"N2"}]
pointers
{"current":"N0"}
phase
"initial"
Insert one fresh adjacent copy and preserve the next original.
Each processed original maps to its adjacent copy; unprocessed originals still have their old next edge.
nodes
[{"id":"N0","value":7,"next":"C0","random":"N2"},{"id":"N1","value":7,"next":"N2","random":"N1"},{"id":"N2","value":9,"next":null,"random":"N2"},{"id":"C0","value":7,"next":"N1","random":null}]
pointers
{"current":"N1"}
phase
"weave"
original
"N0"
copied
"C0"
Insert one fresh adjacent copy and preserve the next original.
Each processed original maps to its adjacent copy; unprocessed originals still have their old next edge.
nodes
[{"id":"N0","value":7,"next":"C0","random":"N2"},{"id":"N1","value":7,"next":"C1","random":"N1"},{"id":"N2","value":9,"next":null,"random":"N2"},{"id":"C0","value":7,"next":"N1","random":null},{"id":"C1","value":7,"next":"N2","random":null}]
pointers
{"current":"N2"}
phase
"weave"
original
"N1"
copied
"C1"
Insert one fresh adjacent copy and preserve the next original.
Each processed original maps to its adjacent copy; unprocessed originals still have their old next edge.
nodes
[{"id":"N0","value":7,"next":"C0","random":"N2"},{"id":"N1","value":7,"next":"C1","random":"N1"},{"id":"N2","value":9,"next":"C2","random":"N2"},{"id":"C0","value":7,"next":"N1","random":null},{"id":"C1","value":7,"next":"N2","random":null},{"id":"C2","value":9,"next":null,"random":null}]
pointers
{"current":null}
phase
"weave"
original
"N2"
copied
"C2"
Translate one random edge through the target’s adjacent copy.
All pairs already exist, so forward, self, backward and shared random targets translate to copies.
nodes
[{"id":"N0","value":7,"next":"C0","random":"N2"},{"id":"N1","value":7,"next":"C1","random":"N1"},{"id":"N2","value":9,"next":"C2","random":"N2"},{"id":"C0","value":7,"next":"N1","random":"C2"},{"id":"C1","value":7,"next":"N2","random":null},{"id":"C2","value":9,"next":null,"random":null}]
pointers
{"current":"N1"}
phase
"random"
original
"N0"
copied
"C0"
Translate one random edge through the target’s adjacent copy.
All pairs already exist, so forward, self, backward and shared random targets translate to copies.
nodes
[{"id":"N0","value":7,"next":"C0","random":"N2"},{"id":"N1","value":7,"next":"C1","random":"N1"},{"id":"N2","value":9,"next":"C2","random":"N2"},{"id":"C0","value":7,"next":"N1","random":"C2"},{"id":"C1","value":7,"next":"N2","random":"C1"},{"id":"C2","value":9,"next":null,"random":null}]
pointers
{"current":"N2"}
phase
"random"
original
"N1"
copied
"C1"
Translate one random edge through the target’s adjacent copy.
All pairs already exist, so forward, self, backward and shared random targets translate to copies.
nodes
[{"id":"N0","value":7,"next":"C0","random":"N2"},{"id":"N1","value":7,"next":"C1","random":"N1"},{"id":"N2","value":9,"next":"C2","random":"N2"},{"id":"C0","value":7,"next":"N1","random":"C2"},{"id":"C1","value":7,"next":"N2","random":"C1"},{"id":"C2","value":9,"next":null,"random":"C2"}]
pointers
{"current":null}
phase
"random"
original
"N2"
copied
"C2"
Restore one original edge and wire one copy edge.
Earlier pairs are separated; later pairs remain woven so their copy translation is still available. Original random fields never change.
nodes
[{"id":"N0","value":7,"next":"N1","random":"N2"},{"id":"N1","value":7,"next":"C1","random":"N1"},{"id":"N2","value":9,"next":"C2","random":"N2"},{"id":"C0","value":7,"next":"C1","random":"C2"},{"id":"C1","value":7,"next":"N2","random":"C1"},{"id":"C2","value":9,"next":null,"random":"C2"}]
pointers
{"current":"N1"}
phase
"separate"
original
"N0"
copied
"C0"
Restore one original edge and wire one copy edge.
Earlier pairs are separated; later pairs remain woven so their copy translation is still available. Original random fields never change.
nodes
[{"id":"N0","value":7,"next":"N1","random":"N2"},{"id":"N1","value":7,"next":"N2","random":"N1"},{"id":"N2","value":9,"next":"C2","random":"N2"},{"id":"C0","value":7,"next":"C1","random":"C2"},{"id":"C1","value":7,"next":"C2","random":"C1"},{"id":"C2","value":9,"next":null,"random":"C2"}]
pointers
{"current":"N2"}
phase
"separate"
original
"N1"
copied
"C1"
Restore one original edge and wire one copy edge.
Earlier pairs are separated; later pairs remain woven so their copy translation is still available. Original random fields never change.
nodes
[{"id":"N0","value":7,"next":"N1","random":"N2"},{"id":"N1","value":7,"next":"N2","random":"N1"},{"id":"N2","value":9,"next":null,"random":"N2"},{"id":"C0","value":7,"next":"C1","random":"C2"},{"id":"C1","value":7,"next":"C2","random":"C1"},{"id":"C2","value":9,"next":null,"random":"C2"}]
pointers
{"current":null}
phase
"separate"
original
"N2"
copied
"C2"
Return the documented outcome after all required mutation or restoration.
The records describe the new graph; Java returns its fresh head. All source edges are restored.
result
[{"id":"C0","value":7,"next":"C1","random":"C2"},{"id":"C1","value":7,"next":"C2","random":"C1"},{"id":"C2","value":9,"next":null,"random":"C2"}]

Backward and null targets

Input: {"values":[4,5],"random":[-1,0]} · Copied graph view: [{"id":"C0","value":4,"next":"C1","random":null},{"id":"C1","value":5,"next":null,"random":"C0"}]

Step 1 of 8: Begin with only original identities.

Original random targets all belong to the acyclic next spine or are null.

Deep copy — original and copied graph edges

Phase: initial. current: N0

N0: 4next → N1random → nullcurrent
N1: 5next → nullrandom → N0

State after this step
Variable	Value
nodes	`[{"id":"N0","value":4,"next":"N1","random":null},{"id":"N1","value":5,"next":null,"random":"N0"}]`
pointers	`{"current":"N0"}`
phase	`"initial"`

See the affected Java block

 1 import java.util.IdentityHashMap;
 2 
 3 public final class Solution {
 4     public static final class Node {
 5         public final int value;
 6         public Node next;
 7         public Node random;
 8         public Node(int value) { this.value = value; }
 9     }
10 
11     public static Node copy(Node head) {
12         if (head == null) return null;
13         Node current = head;
14         while (current != null) {
15             Node copied = new Node(current.value);
16             copied.next = current.next;
17             current.next = copied;
18             current = copied.next;
19         }
20         for (current = head; current != null; current = current.next.next)
21             current.next.random = current.random == null ? null : current.random.next;
22         Node result = head.next;
23         current = head;
24         while (current != null) {
25             Node copied = current.next;
26             Node nextOriginal = copied.next;
27             current.next = nextOriginal;
28             copied.next = nextOriginal == null ? null : nextOriginal.next;
29             current = nextOriginal;
30         }
31         return result;
32     }
33 
34     public static Node baseline(Node head) {
35         IdentityHashMap<Node, Node> copies = new IdentityHashMap<>();
36         for (Node p = head; p != null; p = p.next) copies.put(p, new Node(p.value));
37         for (Node p = head; p != null; p = p.next) {
38             Node copied = copies.get(p);
39             copied.next = copies.get(p.next);
40             copied.random = copies.get(p.random);
41         }
42         return copies.get(head);
43     }
44 }
45

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Begin with only original identities.
Original random targets all belong to the acyclic next spine or are null.
nodes
[{"id":"N0","value":4,"next":"N1","random":null},{"id":"N1","value":5,"next":null,"random":"N0"}]
pointers
{"current":"N0"}
phase
"initial"
Insert one fresh adjacent copy and preserve the next original.
Each processed original maps to its adjacent copy; unprocessed originals still have their old next edge.
nodes
[{"id":"N0","value":4,"next":"C0","random":null},{"id":"N1","value":5,"next":null,"random":"N0"},{"id":"C0","value":4,"next":"N1","random":null}]
pointers
{"current":"N1"}
phase
"weave"
original
"N0"
copied
"C0"
Insert one fresh adjacent copy and preserve the next original.
Each processed original maps to its adjacent copy; unprocessed originals still have their old next edge.
nodes
[{"id":"N0","value":4,"next":"C0","random":null},{"id":"N1","value":5,"next":"C1","random":"N0"},{"id":"C0","value":4,"next":"N1","random":null},{"id":"C1","value":5,"next":null,"random":null}]
pointers
{"current":null}
phase
"weave"
original
"N1"
copied
"C1"
Translate one random edge through the target’s adjacent copy.
All pairs already exist, so forward, self, backward and shared random targets translate to copies.
nodes
[{"id":"N0","value":4,"next":"C0","random":null},{"id":"N1","value":5,"next":"C1","random":"N0"},{"id":"C0","value":4,"next":"N1","random":null},{"id":"C1","value":5,"next":null,"random":null}]
pointers
{"current":"N1"}
phase
"random"
original
"N0"
copied
"C0"
Translate one random edge through the target’s adjacent copy.
All pairs already exist, so forward, self, backward and shared random targets translate to copies.
nodes
[{"id":"N0","value":4,"next":"C0","random":null},{"id":"N1","value":5,"next":"C1","random":"N0"},{"id":"C0","value":4,"next":"N1","random":null},{"id":"C1","value":5,"next":null,"random":"C0"}]
pointers
{"current":null}
phase
"random"
original
"N1"
copied
"C1"
Restore one original edge and wire one copy edge.
Earlier pairs are separated; later pairs remain woven so their copy translation is still available. Original random fields never change.
nodes
[{"id":"N0","value":4,"next":"N1","random":null},{"id":"N1","value":5,"next":"C1","random":"N0"},{"id":"C0","value":4,"next":"C1","random":null},{"id":"C1","value":5,"next":null,"random":"C0"}]
pointers
{"current":"N1"}
phase
"separate"
original
"N0"
copied
"C0"
Restore one original edge and wire one copy edge.
Earlier pairs are separated; later pairs remain woven so their copy translation is still available. Original random fields never change.
nodes
[{"id":"N0","value":4,"next":"N1","random":null},{"id":"N1","value":5,"next":null,"random":"N0"},{"id":"C0","value":4,"next":"C1","random":null},{"id":"C1","value":5,"next":null,"random":"C0"}]
pointers
{"current":null}
phase
"separate"
original
"N1"
copied
"C1"
Return the documented outcome after all required mutation or restoration.
The records describe the new graph; Java returns its fresh head. All source edges are restored.
result
[{"id":"C0","value":4,"next":"C1","random":null},{"id":"C1","value":5,"next":null,"random":"C0"}]

Empty random-pointer list

Input: {"values":[],"random":[]} · Copied graph view: []

Step 1 of 2: Begin with only original identities.

Original random targets all belong to the acyclic next spine or are null.

Deep copy — original and copied graph edges

Phase: initial. current: null

No nodes at this step.

State after this step
Variable	Value
nodes	`[]`
pointers	`{"current":null}`
phase	`"initial"`

See the affected Java block

 1 import java.util.IdentityHashMap;
 2 
 3 public final class Solution {
 4     public static final class Node {
 5         public final int value;
 6         public Node next;
 7         public Node random;
 8         public Node(int value) { this.value = value; }
 9     }
10 
11     public static Node copy(Node head) {
12         if (head == null) return null;
13         Node current = head;
14         while (current != null) {
15             Node copied = new Node(current.value);
16             copied.next = current.next;
17             current.next = copied;
18             current = copied.next;
19         }
20         for (current = head; current != null; current = current.next.next)
21             current.next.random = current.random == null ? null : current.random.next;
22         Node result = head.next;
23         current = head;
24         while (current != null) {
25             Node copied = current.next;
26             Node nextOriginal = copied.next;
27             current.next = nextOriginal;
28             copied.next = nextOriginal == null ? null : nextOriginal.next;
29             current = nextOriginal;
30         }
31         return result;
32     }
33 
34     public static Node baseline(Node head) {
35         IdentityHashMap<Node, Node> copies = new IdentityHashMap<>();
36         for (Node p = head; p != null; p = p.next) copies.put(p, new Node(p.value));
37         for (Node p = head; p != null; p = p.next) {
38             Node copied = copies.get(p);
39             copied.next = copies.get(p.next);
40             copied.random = copies.get(p.random);
41         }
42         return copies.get(head);
43     }
44 }
45

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Begin with only original identities.
Original random targets all belong to the acyclic next spine or are null.
nodes
[]
pointers
{"current":null}
phase
"initial"
Return the documented outcome after all required mutation or restoration.
The records describe the new graph; Java returns its fresh head. All source edges are restored.
result
[]

Test the contract

Input: null
Output: null
Empty copy.
Input: One node, random=self
Output: Fresh node, random=copy itself
Self relation translated.
Input: Equal-valued nodes with null, backward, and shared targets
Output: Distinct copies preserving every edge
Identity graph structure.
Input: All random assignments for next lengths 0..5
Output: Graph-isomorphic fresh copies; restored source
Exhaustive bounded graph oracle.
Input: 100,000-node next chain, mirrored random targets
Output: Fresh complete graph; source unchanged
Iterative size boundary without recursion.

Common mistakes and counterexamples

Copy values but retain original random targets

Counterexample: C0.random=N2 breaks deep-copy independence even if the values look correct.

Translate every target through the identity map or woven target.next.

Use value as the map key

Counterexample: N0(7) and N1(7) would collapse into one copied object.

Map by original reference identity; exhaustive all-equal fixtures expose this.

Assign random during initial insertion

Counterexample: A forward random target has not yet received a copy.

Complete weaving for the whole spine before the random pass.

Forget to restore source links

Counterexample: The copy can look correct while callers now traverse twice as many mixed nodes.

Check every original next/random edge after return and check copied edges reference only copied identities.

Claim interleaving is strongly exception-safe

Counterexample: Failure to allocate the kth copy can leave earlier pairs published.

Document the failure contract and use the nonmutating map implementation when it is required.

Follow-ups

The source is read-only or shared concurrently.

Use the explicit identity-map baseline. Even complete restoration on return does not make temporary mixed original/copy links safe for another reader.

The next graph may contain cycles or random targets outside the spine.

Treat the structure as a general graph and use an identity map plus BFS/DFS over every permitted edge. Define the reachable copy domain; the linear spine and adjacent-copy proofs no longer apply.

Require source preservation if allocation fails.

Prefer the map approach, which does not publish writes into original nodes. A rollback-capable interleaving variant needs a reliably tracked partial prefix and recovery proof; it cannot be inferred from this normal-completion algorithm.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 118/20,000 characters

Self-review

I distinguish next-chain acyclicity from allowed random cycles.I can prove each of the three passes separately.I test graph isomorphism, copy/source disjointness, repeated-call freshness, and every original edge.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Linked lists: identity, reachability, and update order

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-16 · Original teaching content and implementations authored for AceYourInterviews. Standard problem names do not imply company-frequency or external platform-difficulty claims.