Merge k Sorted Lists

HardLinked List

Merge k sorted linked lists into one sorted linked list and return its head.

Constraints

0 <= k <= 10^4
Total nodes <= 10^4

Min-heap of list heads

Time O(N log k)Space O(k)

Push the head of every list into a min-heap keyed by value. Repeatedly pop the smallest node, append it to the result, and push its next node.

#include <bits/stdc++.h>
using namespace std;

struct ListNode { int val; ListNode* next; };

ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
    for (ListNode* l : lists) if (l) pq.push(l);
    ListNode dummy(0), *tail = &dummy;
    while (!pq.empty()) {
        ListNode* node = pq.top(); pq.pop();
        tail->next = node; tail = node;
        if (node->next) pq.push(node->next);
    }
    return dummy.next;
}