Copy List with Random Pointer
Asked at Amazon, Microsoft, Oracle
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Amazon | Medium | View all Amazon questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Oracle | Medium | View all Oracle 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.
Visual walkthrough for list: 1 -> 2 -> 3, with 1.random = 3, 2.random = 1, 3.random = null:
Interleave: 1 -> 1' -> 2 -> 2' -> 3 -> 3'
Set random: 1'.random = 1.random.next = 3.next = 3'
2'.random = 2.random.next = 1.next = 1'
3'.random = null (3.random is null)
Separate: original: 1 -> 2 -> 3. copy: 1' -> 2' -> 3'.
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).
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
class 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Copy List with Random Pointer?
Copy List with Random Pointer is asked at Amazon, Microsoft, Oracle. 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.