Merge Two Sorted Lists
Merge two sorted linked lists into one sorted list and return its head.
- The number of nodes in both lists is in the range [0, 50].
- -100 <= Node.val <= 100
- Both list1 and list2 are sorted in non-decreasing order.
Intuition
Merge two sorted lists combines two sorted linked lists into one sorted list, splicing the existing nodes rather than allocating new ones.
The merge itself mirrors the merge step of merge sort: compare the two heads, take the smaller, and advance that list. What makes the linked-list version fiddly is the bookkeeping around the head of the result.
A dummy node removes that entirely:
- Build onto a dummy head, so every append is identical and no branch is needed to establish the first node.
Without it, the first append is a special case — the result head must be set rather than linked onto — and that special case appears in every loop iteration as a conditional.
With a dummy, a tail pointer always has somewhere to attach. Return dummy.next at the end, which is the real head.
One list is exhausted before the other, and the remainder must be attached. Because both lists are already sorted and everything remaining is larger than everything placed, the whole remainder can be linked in one assignment — no loop is required. Walking it node by node works but does unnecessary work.
The comparison should be <= rather than < to keep the merge stable, preserving the relative order of equal values. It does not change correctness here, but it is the right habit.
The recursive version is shorter — return the smaller head with its next set to the merge of the rest — but uses O(m + n) stack space against the iterative version's O(1).
The merge step of merge sort, and the canonical use of a dummy head. Building a list by appending is awkward because the first node is a special case — a throwaway head node removes that branch entirely, and dummy.next is the real answer. Reach for a dummy whenever you're constructing a list front-to-back.
Approach
Before reading on: price up what sorting first costs here, then ask which pointers must be saved before you overwrite anything. Aim for O(m + n) time and O(1) space.
Compare heads and take the smaller
The merge step of merge sort applies directly: compare the two list heads, splice the smaller, and advance that list.
Build behind a dummy node
A dummy head makes every append identical, removing the branch that would otherwise establish the first node on every iteration.
Keep a tail pointer
Track the last node of the result so appends are O(1). Return dummy.next at the end, which is the actual head.
Attach the remainder in one step
Link the entire leftover list with a single assignment. Both lists are sorted and everything remaining exceeds what is placed, so no loop is needed.
Compare with less-than-or-equal
Using <= keeps the merge stable, preserving the order of equal values. It does not affect correctness here but is the right default.
Cost of the merge
Each node is visited once, giving O(m + n) time and O(1) space. The recursive version is shorter but costs O(m + n) stack space.
Solution & live demo
Common pitfalls
Handling the first node as a special case
if not head:
head = tail = pick
else:
tail.next = pick; tail = pickdummy = tail = ListNode(0) ... tail.next = pick; tail = pick
The branch repeats in every iteration for a condition true exactly once. A dummy node makes tail always valid, so the append is unconditional.
Forgetting to attach the leftover tail
while list1 and list2:
...
return dummy.next... tail.next = list1 or list2 return dummy.next
The loop stops when one list empties, leaving the other's remaining nodes unattached and silently dropped. Since both inputs are sorted, whatever remains is already in order and can be linked wholesale.
Using < and losing stability
if list1.val < list2.val:
if list1.val <= list2.val:
The output is identical either way here, but <= preserves the relative order of equal elements — the property that makes merge sort stable. Worth keeping as a habit for when it does matter.
Edge cases
The while loop is skipped and tail.next = list1 or list2 attaches the non-empty list directly.
Nothing is appended; dummy.next is null — the correct empty result.
Using <= (not <) keeps equal values in a stable, predictable order.