← Back to DSA Animator
Copy List with Random Pointer LC #138 Medium Linked List · HashMap
Problem

A linked list of length n is given where each node also has a random pointer which could point to any node in the list or null. Construct a deep copy of the list — brand new nodes with identical structure. The new nodes must not share memory with the original list.

Example 1
Input: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Explanation: Deep copy — same values and same relative pointer structure, but new node objects.
Example 2
Input: [[1,1],[2,1]]
Output: [[1,1],[2,1]]
Explanation: Both random pointers point to the second node in their respective lists.
Constraints: 0 ≤ n ≤ 1000  |  −10⁴ ≤ Node.val ≤ 10⁴  |  Node.random is null or points to some node in the list.
Try Examples
Visualization
 Pass 1 — Create Copy Nodes
Original List (blue)
Copy List (purple · green = fully linked)
HashMap 0
empty
next (original) next (copy) random (original) random (copy) current (orig) current (copy) fully linked
State Variables
Phase
—
curr.val
—
map.size()
0
Step Logic
Press ▶ Play or Next Step to begin the animation.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Pass 1: Walk the original list. For each node create new Node(curr.val) and store map[curr] = copy. Move curr = curr.next.
2
Pass 2: Reset curr = head. Set map[curr].next = map[curr.next].
3
Set map[curr].random = map[curr.random]. Both targets guaranteed to exist.
4
Return map[head] — the head of the deep-copied list.
Time
O(n)
Space
O(n)
Why Two Passes?

Random pointers can jump backwards or forwards — even to the tail from the head. In a single pass, when we try to wire copy.random, the target copy node might not have been created yet.

Pass 1 pre-creates every copy node upfront (no pointers yet). Pass 2 can then safely look up any target via map[orig.random] — it is guaranteed to already exist in the map.