MediumNeetCode150Hash TableLinked List
Copy List with Random Pointer
Deep copy a linked list with next and random pointers.
Examples
Input
head = [[7,null],[13,0],[11,4],[12,0],[5,0],[1,0]]
Output
[[7,null],[13,0],[11,4],[12,0],[5,0],[1,0]]
Deep copy with same structure.
Constraints
- •
0 <= n <= 1000 - •
-10^4 <= Node.val <= 10^4 - •
random is null or index
Approaches
Map old to new nodes.
CodeT: O(n) | S: O(n)
def copyRandomList(head):
if not head: return None
m={}; c=head
while c: m[c]=Node(c.val); c=c.next
c=head
while c:
m[c].next=m.get(c.next)
m[c].random=m.get(c.random)
c=c.next
return m[head]Interleave copies, then split.
CodeT: O(n) | S: O(1) extra
Same as brute.
Diagram
Copy all nodes first, then wire next and random
CodeT: O(n) | S: O(n)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Hash Map | O(n) | O(n) | Map old to new nodes. |
| Interleave + Split | O(n) | O(1) extra | Interleave copies, then split. |
| Hash Map - Optimized | O(n) | O(n) | Same as brute. |
Hash Map
T: O(n)S: O(n)
Map old to new nodes.
Interleave + Split
T: O(n)S: O(1) extra
Interleave copies, then split.
Hash Map - Optimized
T: O(n)S: O(n)
Same as brute.
Common Mistakes
Not handling null random
Forgetting to copy random
Off-by-one