#138
Copy List with Random Pointer
Medium Interleave copies
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Each node has next and random pointers (random can point anywhere or be null). Return a deep copy of the list.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: deep-copy a list whose nodes also have a random pointer.
Why this works: put each copy right after its original. Then copy.random = original.random.next, and finally split the two lists.
Example: A(random C) → B → C
A → A' → B → B' → C → C'A'.random = A.random.next = C'split → A' → B' → C'
✦Hints open one at a time
A HashMap old → new makes it easy: O(n) space.
For O(1) extra space, insert each copy right after its original.
Then copy.random = original.random.next, and finally separate the two lists.
↗Approach
Three passes: interleave copies (A → A' → B → B'…), set random pointers of the copies, then unweave to restore the original and extract the copy.
</>Solution (Java)
/*
* class Node { int val; Node next; Node random; Node(int val) { ... } } // provided by LeetCode
*/
class Solution {
public Node copyRandomList(Node head) {
for (Node cur = head; cur != null; cur = cur.next.next) { // 1) interleave
Node copy = new Node(cur.val);
copy.next = cur.next;
cur.next = copy;
}
for (Node cur = head; cur != null; cur = cur.next.next) { // 2) random pointers
if (cur.random != null) cur.next.random = cur.random.next;
}
Node dummy = new Node(0), tail = dummy;
for (Node cur = head; cur != null; cur = cur.next) { // 3) separate
tail.next = cur.next;
tail = tail.next;
cur.next = cur.next.next;
}
return dummy.next;
}
}!Common mistake
Setting copy.random = original.random — that points into the original list, not the copy.
Complexity
- Time: O(n).
- Space: O(1) extra.
Topic: Linked List
🎬 Episodes 40–45: video coming soon