Back to Linked List
Hard
Merge k Sorted Lists
You are given an array of `k` linked-lists `lists`, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.
Examples
Input:lists = [[1,4,5],[1,3,4],[2,6]]
Output:[1,1,2,3,4,4,5,6]
The linked-lists are: [1->4->5, 1->3->4, 2->6]. Merging them into one sorted list yields 1->1->2->3->4->4->5->6.
Input:lists = []
Output:[]
Constraints
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i] is sorted in ascending order.
Approach
Push the head of each linked list into a Min Heap. The heap is ordered by the node's value. Pop the smallest node, attach it to our result list, and if that node has a `next` node, push the `next` node into the heap. Repeat until the heap is empty.
Complexity Analysis
Time Complexity
O(N log k)
Space Complexity
O(k)
Where N is the total number of nodes and k is the number of lists. Space complexity is O(k) for the priority queue.
Solution.java
class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) return null; PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length, (a, b) -> a.val - b.val); for (ListNode node : lists) { if (node != null) { pq.add(node); } } ListNode dummy = new ListNode(0); ListNode tail = dummy; while (!pq.isEmpty()) { ListNode node = pq.poll(); tail.next = node; tail = tail.next; if (node.next != null) { pq.add(node.next); } } return dummy.next; }}