How Do You Clone a Linked List with a Random Pointer?
Learn how to deep-copy a linked list with random pointers using a hash map in O(n) time, with code and interview tips.
Expected Interview Answer
You clone a linked list where each node has both a next pointer and a random pointer (which may point anywhere in the list or to null) by first mapping every original node to a new cloned node using a hash map, then making a second pass to wire up each clone’s next and random pointers using that map, achieving O(n) time and O(n) space.
The first pass creates a new node for every original node and stores the mapping original-node to cloned-node in a hash map, without yet setting any pointers on the clones. The second pass revisits each original node and, using the map, sets clone.next to the mapped clone of original.next and clone.random to the mapped clone of original.random, correctly handling null. An alternative, space-optimized approach interleaves each cloned node directly after its original in the same list (A to A’ to B to B’), which lets you set random pointers using the original’s random.next, then a final pass detaches the interleaved clones back into their own list, dropping space to O(1) extra (excluding the output). The hash-map approach is simpler to reason about and typically preferred unless O(1) space is explicitly required.
- Correctly handles random pointers to null or self
- O(n) time in two clean passes
- Hash-map version is easy to explain and debug
- Interleaving variant achieves O(1) extra space if required
AI Mentor Explanation
Cloning a squad roster where each player also has a designated “buddy” player (who could be anyone, or no one) works in two passes. First, create a blank duplicate card for every player and keep a lookup table mapping each original player to their duplicate card. Second, go through the roster again and, for each player, write their duplicate’s next-teammate and buddy fields by looking up the mapped duplicates in the table, so the new roster mirrors both the batting order and the buddy assignments exactly.
Step-by-Step Explanation
Step 1
First pass: create clones
Walk the original list, creating a new node per original node and mapping original to clone in a hash map.
Step 2
Second pass: wire next pointers
For each original node, set clone.next to map[original.next], or null if original.next is null.
Step 3
Second pass: wire random pointers
For each original node, set clone.random to map[original.random], or null if original.random is null.
Step 4
Return the cloned head
map[original_head] is the head of the fully wired clone list.
What Interviewer Expects
- Explain why a naive single pass fails (random may point to a not-yet-cloned node)
- Describe the hash-map two-pass approach clearly
- Correctly state O(n) time and O(n) space
- Mention the O(1)-extra-space interleaving alternative when asked to optimize
Common Mistakes
- Trying to clone in a single pass and setting random to the wrong (original, not cloned) node
- Forgetting to handle random or next pointers that are null
- Not mapping the original head itself, causing a lookup failure when returning the result
- Mutating the original list without restoring it when using the interleaving approach
Best Answer (HR Friendly)
“I make two passes: first I create a blank copy of every node and remember which original maps to which copy in a hash map. Then I go through again and use that map to correctly wire up each copy’s next and random pointers, so the clone perfectly mirrors the structure, including the random links, without ever pointing back into the original list.”
Code Example
class Node:
def __init__(self, val, next=None, random=None):
self.val = val
self.next = next
self.random = random
def copy_random_list(head):
if not head:
return None
mapping = {}
node = head
while node:
mapping[node] = Node(node.val)
node = node.next
node = head
while node:
mapping[node].next = mapping.get(node.next)
mapping[node].random = mapping.get(node.random)
node = node.next
return mapping[head]Follow-up Questions
- How would you solve this with O(1) extra space instead of a hash map?
- Why does a naive single-pass clone fail for the random pointer?
- How would you verify the clone is a deep copy and not sharing any nodes with the original?
- How would this change if random could point to a node not yet created in a streaming scenario?
MCQ Practice
1. Why can’t you reliably clone this list in a single forward pass?
random may point forward to a node not yet visited, so its clone does not exist yet in a single pass.
2. What is the space complexity of the hash-map based cloning approach?
The hash map stores one entry per node, giving O(n) additional space.
3. What technique reduces this problem to O(1) extra space?
Interleaving each clone right after its original lets you use original.random.next to set the clone’s random pointer without a hash map.
Flash Cards
What two passes does the hash-map cloning approach use? — First pass creates clones and maps originals to clones; second pass wires next and random using the map.
Why does a single forward pass fail for this problem? — random can point to a node ahead that has not been cloned yet.
What is the time and space complexity of the hash-map approach? — O(n) time and O(n) space.
What alternative technique achieves O(1) extra space? — Interleaving cloned nodes directly after their originals, then detaching them in a final pass.