138. Copy List with Random Pointer
Asked at Amazon, Microsoft, Oracle, Bloomberg and 1 more
Difficulty
Medium
Time
O(n)
Space
O(n)
Pattern
Hash Table
Companies
5
Problem
You are given the head of a linked list. Each node holds a value, a next pointer, and one extra random pointer. The random pointer may point to any node in the list, or it may be null.
Your job is to build a deep copy of the whole list. A deep copy means every node in the new list is a brand new object. No pointer in the new list may point to a node of the original list. The new list must have the same length, the same values in the same order, and the same shape of random links. So if node X points to node Y in the original list, then the copy of X must point to the copy of Y.
Return the head of the copied list. If the input list is empty, return null.
In the examples, a node is written as [val, random_index], where random_index is the position the random pointer targets, or null if it targets nothing. Your function only receives the head node, not this array form.
A list with an extra random pointer
Constraints
- ●
0 <= n <= 1000 - ●
-10^4 <= Node.val <= 10^4 - ●
Node.random is null or points to some node in the same list
Examples
head = [[7,null],[13,0],[11,4],[10,2],[1,0]][[7,null],[13,0],[11,4],[10,2],[1,0]]head = [[1,1],[2,1]][[1,1],[2,1]]head = [[3,null],[3,0],[3,null]][[3,null],[3,0],[3,null]]Asked At
5 companies| Company | Difficulty | |
|---|---|---|
| Amazon | Medium | View all Amazon questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Oracle | Medium | View all Oracle questions → |
| Bloomberg | Medium | View all Bloomberg questions → |
| NVIDIA | Medium | View all NVIDIA questions → |
How to Think About It
Hash map approach: iterate through the original list, creating a copy of each node and storing the mapping original -> copy in a hash map. Then iterate again, setting the next and random pointers of each copy using the hash map. Time: O(n), space: O(n).
The hash map maps original nodes to their copies. On the first pass, create all copy nodes. On the second pass, for each original node, set copy.next = hash_map[original.next] and copy.random = hash_map[original.random]. Handle null pointers.
Interleaving approach (optimal space): for each original node orig, insert a copy copy right after orig in the list. So the list becomes: orig1 -> copy1 -> orig2 -> copy2 -> .... Then set copy.random = orig.random.next (if orig.random exists). Finally, separate the original and copy lists.
The interleaving approach uses O(1) extra space (the copies are part of the list). The separation step preserves the original list structure if needed, or destroys it if not.
Time: O(n) for both approaches. Space: O(n) for hash map, O(1) for interleaving.
Optimal Approach
Hash map approach:
- Iterate through the original list. For each node, create a copy and store
original -> copyin ahash map. - Iterate again. For each original node, set
copy.next = hash_map[original.next](ornull) andcopy.random = hash_map[original.random](ornull). - Return
hash_map[head].
Walkthrough: 1 -> 2 -> 3, 1.random=3, 2.random=1, 3.random=null
- Pass 1:
{1: 1', 2: 2', 3: 3'} - Pass 2:
1'.next = hash[2] = 2',1'.random = hash[3] = 3'2'.next = hash[3] = 3',2'.random = hash[1] = 1'3'.next = null,3'.random = null
- Result:
1' -> 2' -> 3'with correct random pointers.
Time: O(n). Space: O(n).
Two passes with a hash map
What Trips People Up in Real Interviews
Forgetting to handle null pointers. Both next and random can be null. When setting pointers, check if the original pointer is null before looking up the hash map. hash_map[null] will cause a key error.
Setting random before next or vice versa. The order doesn't matter because both passes use the original list for lookups. But if you try to do it in one pass, you will fail because the copy's neighbors might not exist yet.
Trying to do it in one pass without a hash map. The interleaving approach requires three passes (interleave, set random, separate). Attempting one pass without a hash map leads to missing random pointers.
Confusing deep copy with shallow copy. A shallow copy shares nodes with the original. A deep copy creates entirely new nodes. The hash map ensures each original node maps to exactly one new node.
Not returning the correct head. After building the copy, return hash_map[head], not head. Returning head gives the original list, not the copy.
Solution Code
O(n) timeclass Node:
def __init__(self, val=0, next=None, random=None):
self.val = val
self.next = next
self.random = random
class Solution:
def copyRandomList(self, head):
if not head:
return None
mapping = {}
curr = head
while curr:
mapping[curr] = Node(curr.val)
curr = curr.next
curr = head
while curr:
if curr.next:
mapping[curr].next = mapping[curr.next]
if curr.random:
mapping[curr].random = mapping[curr.random]
curr = curr.next
return mapping[head]Frequently Asked Questions
What is the Copy List with Random Pointer problem?
A linked list of length n is given where each node has an additional random pointer that 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 corresponding original node's value and its next and random pointers set to the corresponding new node's next and random pointers.
How do you solve Copy List with Random Pointer?
The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Copy List with Random Pointer?
Copy List with Random Pointer is asked at Amazon, Microsoft, Oracle, Bloomberg, NVIDIA. It is a medium difficulty problem.
What are common mistakes on Copy List with Random Pointer?
- Forgetting to handle `null` pointers. Both `next` and `random` can be `null`. When setting pointers, check if the original pointer is `null` before looking up the `hash map`. `hash_map[null]` will cause a key error.
- Setting `random` before `next` or vice versa. The order doesn't matter because both passes use the original list for lookups. But if you try to do it in one pass, you will fail because the copy's neighbors might not exist yet.
- Trying to do it in one pass without a `hash map`. The interleaving approach requires three passes (interleave, set random, separate). Attempting one pass without a `hash map` leads to missing random pointers.
- Confusing deep copy with shallow copy. A shallow copy shares nodes with the original. A deep copy creates entirely new nodes. The `hash map` ensures each original node maps to exactly one new node.
- Not returning the correct head. After building the copy, return `hash_map[head]`, not `head`. Returning `head` gives the original list, not the copy.