ASAPUtils
The reframe
Do not search both lists. Their sorted order exposes exactly two candidates: the current heads. A
single tail grows a final sorted prefix.
Invariant
Everything from
dummy.nextthroughtailis sorted and contains exactly the consumed nodes. Both source pointers still head sorted lists of all remaining nodes.
Optimal solution
ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
ListNode dummy;
ListNode* tail = &dummy;
while (a && b) {
if (a->val <= b->val) {
tail->next = a;
a = a->next;
} else {
tail->next = b;
b = b->next;
}
tail = tail->next;
}
tail->next = a ? a : b;
return dummy.next;
}
function mergeTwoLists(a, b) {
const dummy = new ListNode();
let tail = dummy;
while (a && b) {
if (a.val <= b.val) {
tail.next = a;
a = a.next;
} else {
tail.next = b;
b = b.next;
}
tail = tail.next;
}
tail.next = a ?? b;
return dummy.next;
}
Why the remainder can be attached at once
When one list becomes empty, every node already appended is no greater than the other list’s head. The remaining list is internally sorted, so its whole chain can be attached without more comparisons.
Complexity
At most n+m nodes are examined: O(n+m) time. Existing nodes are reused and only a few references plus one dummy are stored: O(1) auxiliary space.
Traps
- Returning the dummy instead of
dummy.next. - Advancing both inputs after choosing only one.
- Forgetting to advance
tail, repeatedly overwriting the same link. - Allocating a new node for every value when splicing is allowed.
Blank re-solve prompt
State the sorted-prefix invariant, merge
[1,4]with[2,3,8]by hand, then write the dummy/tail implementation in C++ and JavaScript.