# 23. Merge k Sorted Lists

• Time: $O(n\log k)$
• Space: $O(k)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public: ListNode* mergeKLists(vector& lists) { ListNode dummy(0); ListNode* curr = &dummy; auto compare = [](ListNode* a, ListNode* b) { return a->val > b->val; }; priority_queue, decltype(compare)> minHeap( compare); for (ListNode* list : lists) if (list != nullptr) 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; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public ListNode mergeKLists(ListNode[] lists) { ListNode dummy = new ListNode(0); ListNode curr = dummy; Queue 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; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 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