Merge Two Sorted Lists Algorithm
Two sorted lists. Combine them into one sorted list.
12 Mar 2024
Two sorted lists. Combine them into one sorted list.
This is a fundamental building block. Merge sort uses it. Database joins use it. It's one of those problems that looks simple but teaches you a lot about pointer management.
The intuition
Walk through both lists at the same time. Compare the current elements. Pick the smaller one and move that pointer forward. Repeat until one list runs out, then tack on whatever's left.
The code (array version)
Javascript
const mergeSortedArrays = (arr1, arr2) => {
const result = [];
let i = 0;
let j = 0;
while (i < arr1.length && j < arr2.length) {
if (arr1[i] <= arr2[j]) {
result.push(arr1[i++]);
} else {
result.push(arr2[j++]);
}
}
while (i < arr1.length) result.push(arr1[i++]);
while (j < arr2.length) result.push(arr2[j++]);
return result;
};
mergeSortedArrays([2, 3, 8, 12], [4, 5, 9, 14]);
// [2, 3, 4, 5, 8, 9, 12, 14]The code (linked list version)
For the classic LeetCode version with linked lists:
Javascript
var mergeTwoLists = function(list1, list2) {
const dummy = { val: 0, next: null };
let current = dummy;
while (list1 && list2) {
if (list1.val <= list2.val) {
current.next = list1;
list1 = list1.next;
} else {
current.next = list2;
list2 = list2.next;
}
current = current.next;
}
current.next = list1 || list2;
return dummy.next;
};Complexity
- Time: O(n + m) — each element is visited once.
- Space: O(n + m) for the array version (new array), O(1) for the linked list version (rewiring existing nodes).
Trade-offs
The dummy node trick avoids special-casing the head of the merged list. A recursive solution is more elegant but uses O(n + m) stack space and risks stack overflow on very long lists. Iterative is safer for production.