visual walkthrough
Merge Two Sorted Lists
Dummy head plus merge, reused in merge sort and k-way merge.
The idea
Both lists are already sorted, so the smallest remaining value is always at the front of one of them. Compare the two fronts, link the smaller one, and repeat.
A dummy node in front of the result means the very first link is handled exactly like every other one.
Complexity
| approach | time | space |
|---|---|---|
| Collect and sort | O((n+m) log(n+m)) | O(n+m) |
| Dummy head and splice | O(n+m) | O(1) |