Difficulty: MediumLinked List

Copy List with Random Pointer

Problem in Plain English

You are given a linked list where each node also has a random pointer to any node or null. Build a deep copy with brand-new nodes that preserves every next and random connection.

Problem Statement

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

Construct a deep copy of the list with exactly n brand-new nodes whose values match the originals and whose next and random pointers mirror the original structure without referencing any original node. Return the head of the copied list.

The displayed pairs are [value, random_index], where indices follow the next chain from zero. Your function receives actual nodes through head, not the pair array. The next chain terminates at null; random links may point backward, forward, to self, or form cycles.

Constraints

0 <= n <= 1000
-10^4 <= Node.val <= 10^4
Node.random is null or points to some node in the same list.

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]]

Label originals O0 through O4 in next order, with values 7,13,11,10,1. Fresh nodes C0 through C4 have next links C0 -> C1 -> C2 -> C3 -> C4 and random targets null,C0,C4,C2,C0. The pair array looks identical, but every node and non-null target belongs exclusively to the new list.

Example 2

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

C0.random and C1.random both target C1. The second node points randomly to itself, so its copy must also point to itself rather than to O1; shared targets remain shared.

Example 3

Input: head = []
Output: []

An empty list copies to an empty list.

Example 4

Input: head = [[3,1],[3,0],[3,null]]
Output: [[3,1],[3,0],[3,null]]

The first two equal-valued nodes form a cycle through random links. Their distinct copies preserve that cycle, while the third copy has a null random. Mapping by value would collapse three different identities incorrectly.

Intuition

Copying values is only half the job: every pointer must reach the corresponding new node, never an original. In Example 1, the copy of 11 must point randomly to the copy of 1 even though that target appears later. Give each original a unique clone first, then translate its connections. A map stores that correspondence explicitly; placing each clone immediately after its original stores the same correspondence in the next links temporarily. Equal values cannot identify nodes, and cycles among random links require no recursion because traversal follows only next.

Approaches

Hash Map Two Passes

Solution Details

Reveal Hash Map Two Passes: intuition, complexity, and code

Intuition

Allocate one new node for each original and store the association by object identity. Once all clones exist, a second next-chain traversal translates both pointers through the map, including forward random targets. This never modifies the originals and is preferable when the input must remain readable throughout the call.

Step-by-Step Logic

Return null for an empty head. Otherwise walk only next and allocate one clone per original, keyed by the original object. Example 1 creates O0 -> C0 through O4 -> C4, with values 7,13,11,10,1.
Reset curr to head after every clone exists. For each original, get its clone and translate the next target through the map; a missing null target yields null. Example 1 wires C0.next=C1 through C3.next=C4, then C4.next=null.
Translate random with the same map and a null check. Example 1 assigns the targets null,C0,C4,C2,C0, including the forward edge from O2 to O4.
Advance curr along the untouched original next chain until null, then return the head mapping C0. Example 1 serializes as [[7,null],[13,0],[11,4],[10,2],[1,0]].

Why It Works

The first pass creates exactly one fresh clone for every original in the terminating next chain. The map is one-to-one by node identity, even when values repeat. In the second pass, replacing each original next or random target with its mapped clone reproduces that edge between the corresponding new nodes; null remains null. All possible random targets already have mappings, including self references and cycles. No pointer in the result reaches an original, and no original field is assigned. Returning the mapping of head therefore returns a structurally identical deep copy with the input unchanged.

Dry Run

Hash Map Two Passes: variable states at each step
action	curr before → after	map addition / clone next	clone random
label originals	O0(7) -> O1(13) -> O2(11) -> O3(10) -> O4(1)	map empty	targets null,O0,O4,O2,O0
allocate	O0 → O1	O0 -> C0(7)	null initially
allocate	O1 → O2	O1 -> C1(13)	null initially
allocate	O2 → O3	O2 -> C2(11)	null initially
allocate	O3 → O4	O3 -> C3(10)	null initially
allocate	O4 → null	O4 -> C4(1); five mappings	null initially
reset	null → O0	all clones exist	—
wire	O0 → O1	C0.next=C1	C0.random=null
wire	O1 → O2	C1.next=C2	C1.random=C0
wire	O2 → O3	C2.next=C3	C2.random=C4
wire	O3 → O4	C3.next=C4	C3.random=C2
wire	O4 → null	C4.next=null	C4.random=C0
return	null	map[head]=C0; original unchanged	[[7,null],[13,0],[11,4],[10,2],[1,0]]

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(n)

With n original nodes, two next-chain passes allocate n clones and translate 2n edges. Identity-map operations take expected constant time, giving expected O(n) time; this assumes ordinary hash-table behavior rather than a universal worst-case collision bound. Java explicitly uses IdentityHashMap; Python objects keep identity hashing, and JavaScript Map keys are objects. The map uses O(n) auxiliary storage and the required returned nodes use another O(n), so total space remains O(n). Null needs no allocated clone. Originals are never modified.

Code

Solution.java

1import java.util.Map;2import java.util.IdentityHashMap;3
4// Omit this definition when the platform supplies Node.5class Node {6    int val;7    Node next, random;8    Node(int val) { this.val = val; }9}10
11class Solution {12    public Node copyRandomList(Node head) {13        if (head == null) return null;14        Map<Node, Node> oldToNew = new IdentityHashMap<>();15        Node curr = head;16        while (curr != null) {17            oldToNew.put(curr, new Node(curr.val));18            curr = curr.next;19        }20        curr = head;21        while (curr != null) {22            Node copy = oldToNew.get(curr);23            copy.next = oldToNew.get(curr.next);24            copy.random = oldToNew.get(curr.random);25            curr = curr.next;26        }27        return oldToNew.get(head);28    }29}

Hints

Hint 1

A clone whose random points forward cannot be wired until that target clone exists, so separate creation from wiring.

Hint 2

First map every original node to a fresh copy, then translate each next and random through the map with null mapping to null.

Hint 3

To drop the map, weave each copy after its original so original.random.next is exactly the clone the random link needs.

Edge Cases

An empty head returns null immediately without entering any loop.
A node whose random points to itself must have its clone point to itself, not to the original.
Several nodes sharing one random target must all resolve to the same single clone.
Equal-valued nodes are distinct identities; random cycles and shared targets must be preserved inside the copied list.
A 1000-node list with randoms pointing backward or forward still needs exactly 1000 fresh nodes; random edges do not drive traversal.

Common Mistakes and Interview Tips

Reading curr.random.next without a null check, which crashes on nodes whose random is null.
Leaving the original list interwoven after the split instead of restoring its next chain.
Shallow-copying by reusing original nodes for next or random instead of their mapped clones.
Keying the map by value rather than node identity, which merges distinct equal-valued nodes.
Separating pairs before finishing the random pass, so target.next no longer always denotes its clone.
Following random edges during traversal without tracking visits; a self pointer or random cycle can then loop forever.

Key Takeaway

When clones must preserve cross-links, either map originals to copies first or weave copies inline so each target is reachable without a map.