Merge Two Sorted Lists
Merge two sorted linked lists into one sorted list and return its head.
Open on LeetCode ↗Intuition
Both lists are sorted, so the next node of the result is always the smaller of the two current heads. A dummy head removes the awkward special case for the very first node.
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
Don't throw away the existing sort
Collecting every value, sorting, and rebuilding works but ignores that both inputs are already sorted — and it allocates a whole new structure. Since the lists are sorted, the next node of the merged result is always just the smaller of the two current heads, which we can decide one node at a time in linear time.
Use a dummy head to avoid edge cases
Building a linked list incrementally has an annoying wrinkle: the very first node has no predecessor to attach to, forcing a special case. A throwaway dummy node fixes this — tail starts at the dummy and always has somewhere to append, and at the end we return dummy.next, discarding the placeholder. This keeps the loop body uniform.
Compare heads, then splice the remainder
While both lists have nodes, attach the smaller head to tail and advance that list (using <= rather than < keeps equal values in a stable order). Once one list empties, the other is already sorted, so tail.next = list1 or list2 splices its entire remainder on in a single step — no need to walk it. O(m + n) time, O(1) space, no new nodes.
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.