Copy List with Random Pointer

Explanation & Solution

Description

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

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

The input is given as an array of [val, randomIndex] pairs, where randomIndex is the index of the node that the random pointer points to, or null if it points to nothing.

Return the deep copy in the same [val, randomIndex] format.

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Explanation:

Node 0: val=7, random→null
Node 1: val=13, random→node 0 (val 7)
Node 2: val=11, random→node 4 (val 1)
Node 3: val=10, random→node 2 (val 11)
Node 4: val=1, random→node 0 (val 7)

Constraints

0 <= n <= 1000
-10⁴ <= Node.val <= 10⁴
random is null or points to a valid node index in the list

Approach

Fast and Slow Pointers pattern

1. Build the Original Linked List

Create node objects from the [val, randomIndex] input array
Wire up next pointers sequentially and random pointers by index
This reconstructs the actual linked list structure in memory

2. Create a Hash Map of Copies

Traverse the original list and for each node, create a new copy node with the same value
Store the mapping originalNode → copyNode in a Map
At this point, the copy nodes have no next or random pointers yet

3. Wire Up the Copy Pointers

Traverse the original list again
For each original node, look up its copy in the map
Set copy.next = map.get(original.next) and copy.random = map.get(original.random)
The map ensures we always point to the copy node, never the original

4. Convert Back to Array Format

Traverse the copied list and collect all copy nodes
Build an index map so we can convert node references back to indices
For each copy node, output [val, randomIndex] where randomIndex is the position of the random target in the copy list (or null)

5. Alternative: O(1) Space Interleaving Approach

Interleave: Insert each copy node directly after its original (A → A' → B → B' → ...)
Set random: For each original node, copy.random = original.random.next
Separate: Extract the copy nodes into their own list
This avoids using a hash map but modifies the original list temporarily

🧠 Key Insight

The main difficulty is that random pointers can reference any node, so you cannot copy them until all nodes exist
The hash map approach solves this elegantly: first create all copy nodes, then wire pointers in a second pass

Time

O(n)two passes through the list

Space

O(n)for the hash map storing n node mappings

Visualization

Input:

Linked List Traversal

—

No animation available

Slow (S)Fast (F)Both

0 steps

Solution Code

Flatten a Multilevel Doubly Linked List