Merge K Sorted Lists
You are given an array of k linked-lists, where each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.
Constraints:
- 1 <= k <= 10^4
- 0 <= Node.val <= 10^4
- 0 <= lists.length <= 10^4
- lists[i] has at most 10^4 nodes
- It is guaranteed that the answer will be unique (i.e., the sum of all node values will not exceed 10^7).
Examples:
Input: [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The first linked-list is [1,4,5], the second linked-list is [1,3,4], and the third linked-list is [2,6]. The merged linked-list is [1,1,2,3,4,4,5,6].
Solutions
Priority Queue
We use a priority queue to store the current smallest node from each linked-list. We start by pushing the head of each linked-list into the priority queue. Then, we pop the smallest node from the priority queue and add it to the result linked-list. We also she,Question and the priority queue is empty.
import heapq
def mergeKLists(lists):
minHeap = []
for i in range(len(lists)):
if lists[i]:
heapq.heappush(minHeap, (lists[i].val, i))
lists[i] = lists[i].next
dummy = ListNode(0)
curr = dummy
while minHeap:
val, i = heapq.heappop(minHeap)
curr.next = lists[i]
curr = curr.next
if lists[i].next:
heapq.heappush(minHeap, (lists[i].next.val, i))
lists[i] = lists[i].next
return dummy.nextFollow-up:
How would you optimize the solution if the linked-lists are very large and do not fit into memory?
