Algorithms / Linked List Sorted Merge
Least You Need to Know: Merging Sorted Lists and Splicing Runs
Sorted linked-list merge is a classic interview pattern because the lists are already ordered, so you can advance exactly one front pointer at a time. The algorithm is linear in the total number of nodes and is often implemented cleanly with a dummy head.
The least you need to know
- At each step of a sorted merge, compare the front nodes of the remaining lists.
- Attach the smaller front node and advance only the list it came from.
- When one input is empty, attach the remaining suffix of the other input as-is.
- A dummy head removes annoying first-node branching.
- Merge time is `O(m + n)` because each node is attached once.
Key notation
l1, l2
current fronts of the two sorted lists
tail
end of the merged output so far
m + n
total nodes processed across both lists
Tiny worked example
- Compare the heads of the two lists.
- Attach the smaller node to the merged output and advance that list only.
- Repeat until one list is empty.
- Then attach the untouched remainder of the other list in one step.
Common mistakes
- Students sometimes advance both lists after choosing only one node.
- Students sometimes keep comparing after one list is already empty.
- Stable tie handling matters if the prompt cares about preserving source order.
How to recognize this kind of problem
- Two inputs are already sorted and need to be combined into one sorted result.
- Only front nodes matter at each decision point.
- The problem can be solved by repeated local splicing without extra sorting.
Next recommended lesson
Continue through this topic with Least You Need to Know: Analyzing Loops and Nested Loops.
Least You Need to Know: Analyzing Loops and Nested LoopsRelated lessons
Keep going with nearby lessons in the same topic.