Merge K Sorted Lists
Problem
Given an array of k linked lists, each sorted in ascending order, merge all the lists into one sorted linked list and return it.
Examples
Example 1
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: All 8 nodes merged in sorted order.
Constraints
- •
k == lists.length - •
0 <= k <= 10^4 - •
0 <= list length <= 500
Hints
Hint 1
Merging two sorted lists at a time is easy (see Merge Two Sorted Lists) — merging k of them naively, two at a time in sequence, works but isn't optimal. What if you always merge the two SMALLEST current candidates first?
Hint 2
A min-heap holding one 'current' node from each of the k lists lets you always know which list's next value is globally smallest, in O(log k) instead of scanning all k candidates.
Hint 3
Each time you pop a node from the heap, push its list's NEXT node back in — the heap is always tracking exactly one live candidate per still-active list.
Solutions
public ListNode mergeKListsBruteForce(ListNode[] lists) {
ListNode result = null;
for (ListNode list : lists) {
result = mergeTwoLists(result, list); // reuse the simple two-list merge, one list at a time
}
return result;
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
else { curr.next = l2; l2 = l2.next; }
curr = curr.next;
}
curr.next = (l1 != null) ? l1 : l2;
return dummy.next;
}Time: O(n*k) · Space: O(1) extra beyond the output