Merge two sorted linked lists into one sorted list.
Use a dummy head node to avoid special-casing the result's first element. Walk both lists with two pointers, always appending the smaller current node to the result. When one list is exhausted, append the remainder of the other. O(n + m) time, O(1) space.
How to think about it
Recognise the pattern
This is the merge step of merge sort, applied to linked lists. Two-pointer merge on sorted sequences is a building block you will see again in merge k sorted lists, external sorting, and database join algorithms. Recognise it whenever you need to interleave two ordered sequences optimally.
Build the approach step by step
Brute force: dump both lists into an array, sort, rebuild a linked list. O((n+m) log(n+m)) — wastes the existing sorted order entirely.
Two-pointer merge:
We want to pick the smaller head at each step. The complication with linked lists is handling the very first node without special-casing it. The standard trick: dummy sentinel node.
- Create a
dummy = Node(0)and atailpointer starting there. - While both lists are non-empty: compare
a.valandb.val, attach the smaller totail.next, advance that list’s pointer andtail. - Attach the non-empty remainder directly — no need to walk it.
- Return
dummy.next.
a: 1 -> 3 -> 5
b: 2 -> 4 -> 6
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> 6The dummy node means tail.next = smaller always works — no “is the result empty yet?” check.
Complexity
| Value | Why | |
|---|---|---|
| Time | O(n + m) | Each node visited exactly once |
| Space | O(1) | Rewiring existing nodes; only two extra pointers |