Pattern 4: Merging sorted lists
Merging two sorted lists into a single sorted one is a fundamental operation — and the centerpiece of merge sort. In linked lists it is especially elegant: you copy nothing, you just stitch the pointers.
Try it first: Merge Two Sorted Lists
Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.
Given two sorted linked lists l1 and l2, merge them into a single sorted list and return the head.
Example: 1 → 2 → 4 and 1 → 3 → 4 → 1 → 1 → 2 → 3 → 4 → 4.
Did you try? You can dump everything into an array, sort it, and rebuild — but that ignores the fact that the lists are already sorted and wastes memory. The theory below stitches the two into one in a single pass, with O(1) space.
The theory: stitching with a dummy as guide
Since the two lists are already sorted, the next smallest element of the result is always the head of one of the two. So the algorithm is: compare the heads, take the smaller one, advance that list, repeat.
The delicate part is building the result without special cases for the first node — and this is where the dummy node (lesson 2) shines again:
dummy → (empty)
tail = dummy
while l1 and l2 exist:
if l1.val <= l2.val: tail.next = l1; advance l1
else: tail.next = l2; advance l2
advance tail
tail.next = whatever is left (l1 or l2) ← one of the lists ends first
return dummy.next
The dummy holds the start; the tail is where you "hang" the next smallest
node. At the end, one of the lists empties and the other (whose remainder is
already sorted) is appended all at once.
Why is it O(n + m) time and O(1) space?
Each node of the two lists is visited once as it is stitched into the
result — O(n + m) total, where n and m are the sizes. We create no new nodes or
arrays: we just relink the next pointers of the nodes that already exist, with
a dummy and a tail pointer → O(1) space. (Note that <=, rather than <,
keeps the relative order of equal values — a "stable" property, useful when it
matters.)
Leveling up: Merge k Sorted Lists
What if there are k sorted lists to merge? Two famous strategies, both using the two-list merge as a building block:
- Pairwise merge, tournament-style: merge the lists two at a time, then the results two at a time, and so on (like a knockout tournament). That is log k "rounds", each processing all N elements → O(N log k).
- Min-heap: keep the k heads in a heap and always remove the smallest — you will see this in the Heap section, where this problem reappears.
The takeaway: merging two lists is not just an exercise — it is a building block that scales to much bigger problems.
🧠 Quick-check quiz
0/41. Why does merging two sorted lists not need a sorting step?
2. What is the role of the dummy node in the merge?
3. After one of the lists empties, why is it enough to do tail.next = (the other one)?
4. What is the complexity of merging k lists with the tournament (pairwise) strategy?
Summary
- Merging two sorted lists: compare the heads, stitch the smaller one, advance; a dummy guides and the rest is appended at the end.
- O(n + m) time, O(1) space — it only relinks pointers, it does not copy.
- It is a building block of merging k lists (tournament O(N log k) or heap).
Next lesson: putting it all together — hard problems that combine the middle, reversal, and merge.