## Merge k Sorted Lists

• Time:O(n\log k)
• Space:O(k)

## C++

``````class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode dummy(0);
ListNode* curr = &dummy;
auto compare = [](ListNode* a, ListNode* b) { return a->val > b->val; };
priority_queue<ListNode*, vector<ListNode*>, decltype(compare)> minHeap(
compare);

for (ListNode* list : lists)
if (list)
minHeap.push(list);

while (!minHeap.empty()) {
ListNode* minNode = minHeap.top();
minHeap.pop();
if (minNode->next)
minHeap.push(minNode->next);
curr->next = minNode;
curr = curr->next;
}

return dummy.next;
}
};
``````

## JAVA

``````class Solution {
public ListNode mergeKLists(ListNode[] lists) {
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
Queue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);

for (final ListNode list : lists)
if (list != null)
minHeap.offer(list);

while (!minHeap.isEmpty()) {
ListNode minNode = minHeap.poll();
if (minNode.next != null)
minHeap.offer(minNode.next);
curr.next = minNode;
curr = curr.next;
}

return dummy.next;
}
}
``````

## Python

``````from queue import PriorityQueue

class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
dummy = ListNode(0)
curr = dummy
pq = PriorityQueue()

for i, lst in enumerate(lists):
if lst:
pq.put((lst.val, i, lst))

while not pq.empty():
_, i, minNode = pq.get()
if minNode.next:
pq.put((minNode.next.val, i, minNode.next))
curr.next = minNode
curr = curr.next

return dummy.next
``````