Copy List with Random Pointer
Last Updated: March 29, 2026
Understanding the Problem
On the surface, copying a linked list sounds simple: iterate through the original, create new nodes, wire up next pointers. Done. But the random pointer throws a wrench into that plan. When you're building the copy node by node, the random pointer might reference a node you haven't created yet. You can't set copy.random = original.random because that would point into the original list, not the copy.
So the core challenge is this: how do you map each original node to its corresponding copy so that when it's time to wire up random pointers, you know exactly which copy node to point to?
Key Constraints:
0 <= n <= 1000→ With n up to 1,000, even O(n^2) would be roughly 1 million operations, well within time limits. But O(n) is clearly preferred.-10^4 <= Node.val <= 10^4→ Values can be negative and can repeat, so you cannot use node values as unique identifiers.Node.random is null or points to some node in the list→ Random pointers form arbitrary connections. They're not necessarily forward-pointing, can create cycles, and can point to the node itself.
Approach 1: Hash Map (Two Pass)
Intuition
The most natural way to handle the mapping problem is to use a hash map. In the first pass, we create a copy of every node and store the mapping from original to copy. In the second pass, we wire up both next and random pointers using the map to translate original references into copy references.
This is straightforward and hard to get wrong. The hash map acts as a translator: give it any original node, and it hands back the corresponding copy.
Algorithm
- If
headis null, return null. - First pass: iterate through the original list. For each node, create a new node with the same value and store it in a hash map:
map[original] = copy. - Second pass: iterate through the original list again. For each node, set
map[original].next = map[original.next]andmap[original].random = map[original.random]. - Return
map[head], which is the head of the copied list.
Example Walkthrough
Code
- Time Complexity: O(n). Two passes through the list, each doing O(1) work per node. Hash map operations are O(1) average.
- Space Complexity: O(n). The hash map stores n key-value pairs, one for each node in the original list.
The hash map uses O(n) extra space purely to translate original-to-copy references. What if we could encode that mapping within the list structure itself?
Approach 2: Interleaving Nodes (O(1) Space)
Intuition
Instead of using a hash map, we weave the copy nodes directly into the original list. For each original node A, we insert its copy A' right after it, so the list becomes A -> A' -> B -> B' -> C -> C' -> ...
Now the mapping from original to copy is encoded in the structure itself: original.next is always the copy. For random pointers, if original.random points to some node X, then original.random.next is X's copy. So copy.random = original.random.next. No hash map needed.
After wiring up random pointers, we un-interleave the list to separate the original and copy into two independent lists.
Algorithm
- If
headis null, return null. - Pass 1 (Interleave): For each original node, create a copy and insert it right after the original. A -> B becomes A -> A' -> B -> B'.
- Pass 2 (Set random pointers): For each original node, set
original.next.random = original.random.next. Handle null random pointers. - Pass 3 (Separate lists): Extract the copy nodes into their own list and restore the original list.
- Return the head of the copy list.
Example Walkthrough
Code
- Time Complexity: O(n). Three passes through the list, each doing O(1) work per node.
- Space Complexity: O(1). No hash map or extra data structures. Only a constant number of pointers. The n new nodes are part of the required output.