Clone Linked List with Random
A linked list where each node has an extra pointer (random) that can point to any node in the list (or null). Cloning such a list in O(n) time and O(1) space is a classic hard problem.
Problem: Given a linked list with next and random pointers, create a deep copy.
Efficient Solution (O(n) time, O(1) extra space):
1. Insert copy nodes next to original nodes.
2. Assign random pointers for copies.
3. Extract the copied list.
Implementation:
public static NodeWithRandom clone(NodeWithRandom head) {
if (head == null) return null;
// Step 1: Insert copy nodes
NodeWithRandom curr = head;
while (curr != null) {
NodeWithRandom copy = new NodeWithRandom(curr.val);
copy.next = curr.next;
curr.next = copy;
curr = copy.next;
}
// Step 2: Set random pointers for copies
curr = head;
while (curr != null) {
if (curr.random != null) {
curr.next.random = curr.random.next;
}
curr = curr.next.next;
}
// Step 3: Separate original and copied list
NodeWithRandom newHead = head.next;
NodeWithRandom copyCurr = newHead;
curr = head;
while (curr != null) {
curr.next = curr.next.next;
if (copyCurr.next != null) {
copyCurr.next = copyCurr.next.next;
}
curr = curr.next;
copyCurr = copyCurr.next;
}
return newHead;
}
Two Minute Drill
- Clone a linked list with random pointers in O(n) time and O(1) extra space.
- Three-step approach: interleave copies, assign random, separate.
- This is a classic hard interview problem.
- Requires careful pointer manipulation.
Need more clarification?
Drop us an email at career@quipoinfotech.com