Merge Two Sorted Lists
Problem statement
You are given the heads of two singly linked lists, list1 and list2, and both are already sorted in non-decreasing order. Combine them into a single sorted linked list by reusing the existing nodes — don't create new ones — and return the head of the merged list.
Either list, or both, may be empty.
Examples
Example 1
Input: list1 = [1, 2, 4], list2 = [1, 3, 4]
Output: [1, 1, 2, 3, 4, 4]
Explanation: At each step the smaller of the two current front values is picked next; the two 1s and two 4s both make it in, in the order their lists offered them.

Example 2
Input: list1 = [], list2 = []
Output: []
Explanation: Both lists are empty, so there's nothing to merge.
Example 3
Input: list1 = [], list2 = [0]
Output: [0]
Explanation: One list is empty, so the merged list is simply the other list, unchanged.
Hints
Approach
Optimal: Two pointers with a dummy node, iterative
Intuition
Do the same "always take the smaller front node" idea as recursion, but with a loop instead of function calls, so there's no stack to grow. A dummy node placed just before the real answer gives the loop somewhere to attach the very first real node without a special case — you always attach after tail, and tail always exists from the start.
Steps
- Create a
dummynode and settailto point at it. - While both
list1andlist2still have nodes, compare their front values. - Attach the smaller one after
tail, and move that list's pointer forward past the node just used. - Move
tailforward to the node just attached. - When one list runs out, attach whatever remains of the other list directly — it's already sorted.
- Return
dummy.next(the dummy itself is never part of the answer).
Dry run
list1 = [1, 2, 4], list2 = [1, 3, 4]
| step | compare | attach | list1 left | list2 left |
|---|---|---|---|---|
| 1 | 1 vs 1 | list1's 1 | [2, 4] | [1, 3, 4] |
| 2 | 2 vs 1 | list2's 1 | [2, 4] | [3, 4] |
| 3 | 2 vs 3 | list1's 2 | [4] | [3, 4] |
| 4 | 4 vs 3 | list2's 3 | [4] | [4] |
| 5 | 4 vs 4 | list1's 4 | [] | [4] |
| 6 | list1 empty | attach rest of list2 | [] | [] |
Result: 1 → 1 → 2 → 3 → 4 → 4.
Edge cases: if either list starts empty, the while loop never runs, and the "attach what's left" step immediately returns the other list unchanged.
Complexity
Time O(n+m) - one pass across both lists together; every node is looked at once and attached once.
Space O(1) - extra — beyond the two input lists and one dummy node, nothing new is allocated, and there's no call stack to grow.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeTwoLists(self, list1, list2):
dummy = ListNode()
tail = dummy
while list1 and list2:
if list1.val <= list2.val:
tail.next = list1
list1 = list1.next
else:
tail.next = list2
list2 = list2.next
tail = tail.next
tail.next = list1 if list1 else list2
return dummy.next
def build_list(values):
dummy = ListNode()
tail = dummy
for v in values:
tail.next = ListNode(v)
tail = tail.next
return dummy.next
def to_values(node):
out = []
while node:
out.append(node.val)
node = node.next
return out
if __name__ == "__main__":
print(to_values(Solution().mergeTwoLists(build_list([1, 2, 4]), build_list([1, 3, 4]))))
print(to_values(Solution().mergeTwoLists(build_list([]), build_list([]))))
print(to_values(Solution().mergeTwoLists(build_list([]), build_list([0]))))RecapThe whole problem in a few lines, for the night before
- Spot it: "combine two already-sorted lists into one sorted list"
- Idea: always take the smaller of the two current front nodes; a dummy head avoids a special case for the first pick
- Cost: O(n+m) time; O(1) extra space iteratively (O(n+m) stack recursively)
- Trap: forgetting to attach the leftover tail of whichever list still has nodes once the other one runs out
Interview follow-ups
Merge k sorted linked lists instead of just two.
Repeatedly calling this two-list merge on the lists one pair at a time works but costs O(k · n) in the worst case. A faster way keeps a min-heap holding the current front node of each of the k lists; repeatedly pop the smallest, attach it to the result, and push that list's next node if it has one. That runs in O(N log k) time for N total nodes, since each of the N pops and pushes costs O(log k).
The two lists are too large to hold in memory and arrive as streams (for example, two sorted log files read line by line).
The same two-pointer idea still works without changing its shape: instead of following
nextpointers, read one line at a time from each stream, compare, and write out the smaller one, advancing only that stream's reader. Memory stays O(1) regardless of how large the files are, since only the current line of each stream needs to be held at once.
Frequently asked questions
Sorting throws away the fact that both lists already arrive sorted — that's a fact you get for free, and the optimal approach uses it directly, dropping the cost from O((n+m) log(n+m)) down to O(n+m).
Without it, you'd need an if-check just for the very first node — is the result's head list1's first node or list2's? A dummy node sidesteps that entirely: you always attach after tail, and at the end dummy.next is whatever the first real node turned out to be.
Merging is the core of combining sorted log streams from different hosts by timestamp, or merging sorted shard outputs back into one ordered result — the same "always take the smaller current front item" logic, just applied to log lines or records instead of linked-list nodes.
The problem only requires the merged list to be non-decreasing, so either order is a valid answer for equal values. This solution's <= comparison happens to prefer list1's node on a tie, which is a natural and stable choice, but the checker doesn't require it.
