Merge Two Sorted Lists
On this page
Problem statement
Given the heads of two sorted singly linked lists, merge them into one sorted list by splicing their nodes together, and return its head. Reuse the existing nodes; either list may be empty.
It's the merge step of merge sort on linked lists, and the base case of Merge k Sorted Lists. The clean solution uses a dummy node so the head isn't a special case. Original problem: LeetCode 21.
Example

Input: 1 -> 2 -> 4, 1 -> 3 -> 4
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4
Input: null, 0
Output: 0
Constraints (assumed)
- 0 ≤ nodes in each list ≤ 50.
- Values between −100 and 100; both lists sorted ascending.
What this question tests
- The two-pointer merge on linked lists.
- Using a dummy head to avoid special-casing the first node.
- Not forgetting the leftover part of the longer list.
Questions to ask first
- Can I reuse the input nodes? (Here: yes; splice, don't copy.)
- Sorted ascending, with duplicates allowed? (Yes.)
- Should the merge be stable (equal values from list1 first)? Using
≤gives that. - Iterative or recursive? Either; recursion uses O(n + m) stack.
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.