Merge Two Sorted Lists
Weave the two lists together, always taking the smaller head.
Weave the Two Lists
Problem
Given the heads of two singly linked lists whose values are already sorted in nondecreasing order, combine them into one sorted linked list. Reuse the existing nodes rather than creating a separate collection, and return the head of the combined list.
Examples
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Input: list1 = [], list2 = [0]
Output: [0]
The Goal
Merge two sorted linked lists into one sorted list and return its head. Reuse the nodes: the merge only changes next links.
For [1, 2, 4] and [1, 3, 4], the answer is [1, 1, 2, 3, 4, 4].
Both lists are sorted, so the next node of the answer is always one of the two heads, whichever is smaller.
Take the smaller head
The next node of the answer is the smaller of the two heads. Every node behind a head is at least as big as that head.
Compare two nodes, link one, and move that list on.
Key Idea: A Dummy Head
The first node of the answer is awkward: there's no node before it to link from. So start with a dummy node, and a tail pointer on it.
Every chosen node goes after tail, then tail moves onto it. The first node is handled like every other one. At the end, the answer starts at dummy.next.
Sits in front of the answer and never moves.
dummy → 1 → 1 → 2
The Algorithm
def merge_two_lists(list1, list2):
dummy = tail = ListNode()
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 or list2
return dummy.next<= sends ties to list1. When one list runs out, the rest of the other is already sorted, so one link attaches all of it.
| Approach | Time | Extra space | Trade-off |
|---|---|---|---|
| Dummy head and two pointers | O(n + m) | O(1) | Rewires the nodes in one pass |
| Recursion | O(n + m) | O(n + m) | The call stack grows with the lists |
| Copy values, sort, rebuild | O((n + m) log(n + m)) | O(n + m) | Ignores that the lists are sorted |
Walkthrough
Run it on [1, 2, 4] and [1, 3, 4].
Each node takes four steps on the stage: compare the heads, link the smaller after tail, move its list on, then move tail. The first compare is 1 ≤ 1, a tie, so list1's 1 goes first. Then come list2's 1, list1's 2, list2's 3, and list1's 4, another tie.
That empties list1. list2 still holds a 4, and one link attaches it.
Checkpoint · predict the next step
Step 7 of 23 on the stage: Link it after tail: tail's next is list2's 1.
tail on 1 · list1 on 2 · list2 on 1 · links dummy→1, 1→1, 2→4, 4→None, 1→3, 3→4, 4→None
Pitfalls
- Return
dummy.next, notdummy. The dummy isn't part of the answer. - Move
tailafter every link, or the next node overwrites this one. - Attach the leftover list with one link at the end. There's no need to walk it.
- If both lists are empty,
dummy.nextstaysNone, which is the right answer. - On a tie, either node can go first.
<=takeslist1's.
Why is returning dummy wrong after the merge?
Complexity
Each node is linked once, and each list pointer only moves forward. With n and m nodes, that's at most n + m compares, so time is O(n + m).
The merge keeps dummy, tail, list1 and list2, whatever the lengths, so extra space is O(1). A recursive merge uses O(n + m) stack instead.
One pass, a few pointers
- Compare and linkEach node joins once.O(n + m)
- Attach the restOne link.O(1)
- dummy, tail, list1, list2A fixed number of pointers.O(1)
Linear time, and the merged list is the old nodes, rewired.
In short
Use a dummy head to simplify edge cases. Repeatedly attach the smaller of the two current nodes and advance that list. When one list runs out, link the remainder of the other. The dummy's next is the merged head.
Common mistake
Not using a dummy node, which forces awkward special-casing of the first element.