Linked List · LC #21
Merge Two Sorted Lists
Merge two sorted singly linked lists into one sorted list using a dummy head node and two-pointer comparison. Foundational building block for Merge K Sorted Lists.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.
Sample I/O
Input: l1 = 1→2→4, l2 = 1→3→4 Output: 1→1→2→3→4→4 Input: l1 = [], l2 = [] Output: []
Intuition
How to Think About It
Intuition
Both lists are already sorted, so at each step we only need to compare the current heads and pick the smaller one. A dummy sentinel node before the result eliminates special-casing for the head. After one list is exhausted, the other is already sorted so we can attach it directly.
Core Concept
Create a dummy ListNode and a curr pointer. While both l1 and l2 are non-null, compare their values: attach the smaller node to curr.next and advance that list's pointer, then advance curr. After the loop, attach the non-null remainder (already sorted). Return dummy.next. Time: O(m+n), Space: O(1).
When to use
Merging sorted sequences; serves as the core subroutine in merge sort on linked lists and in Merge K Sorted Lists.
When NOT to use
When lists are unsorted - sort first or use a different approach. When lists are arrays rather than linked lists (use two-pointer index approach instead).
Key Insights
What to Know Cold
- Dummy head node completely eliminates the special case of building the first result node.
- The tail attachment (curr.next = l1 ?? l2) works because the remaining list is already sorted.
- Recursive version is clean but O(m+n) stack space - avoid for very long lists.
- This exact pattern (dummy + curr pointer) recurs in Add Two Numbers and Remove Nth Node.
- Stable sort property: equal elements from l1 appear before l2 because we use <=.
1 example
Worked Examples
Merge 1→2→4 and 1→3→4
Two sorted lists of equal length
Dummy head + iterative comparison
function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
const dummy = new ListNode(0);
let curr = dummy;
while (l1 && l2) {
if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
else { curr.next = l2; l2 = l2.next; }
curr = curr.next!;
}
curr.next = l1 ?? l2;
return dummy.next;
}Output: 1→1→2→3→4→4
Dummy node pattern eliminates edge-case handling - essential pattern used in 5+ other list problems.