1. One-Liner
Merge two sorted singly linked lists into one sorted list by repeatedly taking the smaller head node.
2. The Problem It Solves
Subroutine for merge sort on lists, k-way merge patterns, and ordered stream combination.
3. The Core Idea
Use a dummy node to avoid edge cases; compare heads, advance the smaller pointer, append until one list empties, then attach remainder.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | dummy tail pointer t |
| 2 | While both lists: pick smaller head, advance that list |
| 3 | Append t.next |
| 4 | Attach non-empty tail |
5. Dry Run Example
1→3 and 2→4 merge to 1→2→3→4 with four comparisons in the steady loop.
6. Key Properties
| Property | Detail |
|---|---|
| Stable | If ≤ picks left, stability holds |
| Adaptive | Linear in total length |
| k lists | Heap or divide-merge |
7. Where It Is Used
| Domain / System | Use |
|---|---|
| External sort | Tape merges |
| Logs | Ordered streams |
| Databases | Run merge |
8. Interview Tips
Recursive version is O(n) stack; iterative preferred. For k sorted lists, escalate to heap or pairwise merge.
9. Comparison with Other Algorithms
| Technique | Notes |
|---|---|
| Concat + sort | O(n log n) worse |
| Two arrays | Similar two-pointer |
| Merge k | Heap O(n log k) |
10. Complexity
| -- | -- |
|---|---|
| Time | O(n + m) |
| Space | O(1) pointers |
Implementation Example (PYTHON)
def merge_two(a, b):
dummy = ListNode(0)
t = dummy
while a and b:
if a.val <= b.val:
t.next = a; a = a.next
else:
t.next = b; b = b.next
t = t.next
t.next = a or b
return dummy.next