Merge Two Sorted Lists
Weave two sorted linked lists into one by splicing nodes, using a dummy head to avoid special cases
Problem Statement
You are given the heads of two sorted linked lists. Splice them together into one sorted list and return its head. The result should be made by reusing the existing nodes.
Input: list1 = 1 → 2 → 4
list2 = 1 → 3 → 4
Output: 1 → 1 → 2 → 3 → 4 → 4
Input: list1 = null, list2 = null
Output: null
Input: list1 = null, list2 = 0
Output: 0Intuition
Both lists are already sorted, so the smallest remaining value is always at the front of one list or the other. Compare the two heads, take the smaller, advance that list, repeat. This is the merge step of merge sort, and it is why merge sort is O(n log n).
Unlike Merge Sorted Array, there is no overwrite hazard here — appending to a new list never damages the sources. So the natural front-to-back direction works.
The key insight — use a dummy head
The awkward part is the very first node: is it from list1 or list2? Handling that separately means branching before the loop and again inside it.
Instead, create a throwaway node and build behind it. Every append is then tail.next = node, with no "is this the first one?" question anywhere. At the end, the real head is dummy.next.
The dummy node is one of the highest-value tricks in linked-list problems. It removes an entire class of null-handling bugs for the cost of one allocation.
Real-world analogy
Two sorted stacks of numbered cards being merged into one pile. You look only at the top card of each stack, take the lower, and place it face-down on the new pile. The new pile stays sorted automatically.
Watch it run
Approach
While both lists have nodes
Compare the two head values. Splice the smaller node onto tail.next, advance that list, and move tail forward.
Attach the remainder in one step
When one list empties, the other is already sorted and already linked. tail.next = list1 or list2 finishes the job with a single assignment — no loop.
Return dummy.next
The dummy itself is discarded.
Solution
from typing import Optional
class ListNode:
def __init__(self, val: int = 0, next: Optional["ListNode"] = None):
self.val = val
self.next = next
def merge_two_lists(
list1: Optional[ListNode], list2: Optional[ListNode]
) -> Optional[ListNode]:
"""Merge two sorted lists by splicing their nodes together."""
dummy = ListNode() # placeholder so there is no "first node" special case
tail = dummy
while list1 and list2:
if list1.val <= list2.val: # <= keeps the merge stable
tail.next = list1
list1 = list1.next
else:
tail.next = list2
list2 = list2.next
tail = tail.next
# Exactly one list may have nodes left; it is already sorted.
tail.next = list1 if list1 else list2
return dummy.nextWhy the leftover needs no loop
This is the advantage of linked lists over arrays. In Merge Sorted Array the remaining elements have to be copied one at a time. Here, the remaining nodes are already chained together — a single pointer assignment adopts the whole tail at once.
The recursive version
def merge_two_lists_recursive(
list1: Optional[ListNode], list2: Optional[ListNode]
) -> Optional[ListNode]:
if not list1:
return list2
if not list2:
return list1
if list1.val <= list2.val:
list1.next = merge_two_lists_recursive(list1.next, list2)
return list1
list2.next = merge_two_lists_recursive(list1, list2.next)
return list2It reads beautifully — "the smaller head, followed by the merge of what remains" — but it uses O(n + m) stack frames and can overflow on long lists.
Complexity Analysis
Time Complexity
O(n + m)
Space Complexity
O(1)
- Time — every node from both lists is visited and spliced exactly once.
- Space — the iterative version allocates only the dummy node. No new list is built; the existing nodes are rewired. The recursive version uses
O(n + m)stack space.
Edge Cases
Related Problems
- Merge Sorted Array — the same merge on arrays, where the in-place constraint forces a back-to-front pass
- Reverse Linked List — the other fundamental pointer-rewiring exercise
- Intersection of Two Linked Lists — traversing two lists in step