DSA AnimatorDSA animations
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.

How to solve Copy List with Random Pointer

LeetCode 138 · Medium · Linked List · Pattern: Interleaving

Why the obvious approach is slow

A hash map from each old node to its copy works in two passes. But it uses O(n) extra space.

The key idea

First, insert each copy right after its original, so the list alternates old and new. Then each copy's random is the original's random dot next. Finally, split the list back into the original and the copy.

Remember

Put each copy right after its original. Then the copy of a node's random is just random dot next.

Run the animation above on your own input, or watch the 1:30 video explanation of Copy List with Random Pointer with a dry run and Java code.

More Linked List problems