Given an array of k linked lists, each sorted in ascending order, merge all the lists into one sorted linked list and return it.
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.
k == lists.length0 <= k <= 10^40 <= list length <= 500Merging 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?
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.
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.
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> minHeap = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));
for (ListNode head : lists) if (head != null) minHeap.offer(head);
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (!minHeap.isEmpty()) {
ListNode smallest = minHeap.poll();
tail.next = smallest;
tail = tail.next;
if (smallest.next != null) minHeap.offer(smallest.next); // push this list's next candidate
}
return dummy.next;
}Time: O(n log k), n = total nodes across all lists · Space: O(k)