ASAPUtils
The reframe
The hard part is translating an original node reference into the corresponding copied reference. A map does that directly. Interleaving encodes the same mapping physically:
original A → copy A → original B → copy B
Therefore original.random.next is copy.random.
O(1)-auxiliary-space solution
Node* copyRandomList(Node* head) {
if (!head) return nullptr;
for (Node* p = head; p; p = p->next->next) {
Node* copy = new Node(p->val);
copy->next = p->next;
p->next = copy;
}
for (Node* p = head; p; p = p->next->next) {
p->next->random = p->random ? p->random->next : nullptr;
}
Node* copyHead = head->next;
for (Node* p = head; p;) {
Node* copy = p->next;
p->next = copy->next;
p = p->next;
copy->next = p ? p->next : nullptr;
}
return copyHead;
}
function copyRandomList(head) {
if (!head) return null;
for (let p = head; p; p = p.next.next) {
const copy = new Node(p.val);
copy.next = p.next;
p.next = copy;
}
for (let p = head; p; p = p.next.next) {
p.next.random = p.random ? p.random.next : null;
}
const copyHead = head.next;
for (let p = head; p;) {
const copy = p.next;
p.next = copy.next;
p = p.next;
copy.next = p ? p.next : null;
}
return copyHead;
}
Three-pass proof
After pass one, every original is followed by exactly its own copy. Pass two assigns each copied random edge using that adjacency, including null edges. Pass three restores every original next edge and links every copy to the next copy. The lists end independent and structurally equivalent.
Complexity
Three linear passes are O(n) time. Apart from the n result nodes required by the answer, only pointers are used: O(1) auxiliary space.
Traps
- Setting
copy.random = original.random, which points into the original list. - Separating the lists before all random edges have been translated.
- Advancing one step rather than two through the interleaved list.
- Counting output nodes as auxiliary space; the copy itself is required output.
Blank re-solve prompt
Say the three verbs “interleave, wire, separate.” Derive the expression for a copied random target instead of memorising it, then code the null cases.