#21
Merge Two Sorted Lists
Easy Dummy head merge
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Merge two sorted linked lists into one sorted list by splicing their nodes together.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: zip two sorted lists into one sorted list.
Why this works: the next node is always the smaller of the two heads; a dummy node holds the start.
Example: 1→2→4 and 1→3→4
1, 1, 2, 3, 4, 4✦Hints open one at a time
A dummy node in front of the result avoids special-casing the head.
Attach the smaller of the two current nodes, then move on in that list.
↗Approach
tail starts at a dummy node. While both lists have nodes, link the smaller one after tail. Attach whatever is left at the end.
</>Solution (Java)
/**
* class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } // provided by LeetCode
*/
class Solution {
public ListNode mergeTwoLists(ListNode a, ListNode b) {
ListNode dummy = new ListNode(0), tail = dummy;
while (a != null && b != null) {
if (a.val <= b.val) { tail.next = a; a = a.next; }
else { tail.next = b; b = b.next; }
tail = tail.next;
}
tail.next = (a != null) ? a : b; // leftovers are already sorted
return dummy.next;
}
}!Common mistake
Forgetting to attach the leftover list after the loop.
Complexity
- Time: O(n + m).
- Space: O(1).
Topic: Linked List
🎬 Episodes 40–45: video coming soon