Merge k Sorted Lists — Editorial

Opening the reading…

Intuitionwhy one candidate per list is enough

The next value in the merged list must be the smallest value currently visible at the front of any input list. Once you choose that node, the next node from the same list becomes its only possible replacement; every other list keeps the same front value. The problem therefore reduces to repeatedly choosing the smallest among at most k current heads.

A min-heap is built for exactly this repeated choice. Start by placing the head of every non-empty list into the heap. Remove the smallest head, attach it to the result, and insert its next node if one exists. The heap never stores every node at once: it stores one frontier node per list, which keeps each selection at O(log k) instead of scanning all lists.

Approach

Create a linked list for each non-empty integer array and push its head into a min-heap, because empty arrays have no candidate and must not be indexed at position 0.

Use a dummy node and a tail pointer for the result, because attaching the first selected node should use the same operation as attaching every later node.

While the heap is not empty, remove its smallest node, because that node is the smallest value among all currently available list heads and therefore must be next in sorted order.

Attach the removed node to tail and advance tail, because leaving the node in place or copying values separately would lose the linked-list order the result must return.

If the removed node has a next node, push that successor into the heap, because the selected list needs exactly one replacement candidate after its front is consumed.

Return dummy.next, because the dummy simplifies construction but is not part of the required output list.

Complexitycounting heap work and returned nodes separately

MEASURE	BOUND	WHY
Time	O(n log k)	Each of the n nodes is inserted into the heap at most once and removed exactly once. The heap contains at most k nodes, so each operation costs O(log k); converting the arrays into linked nodes adds O(n) work, which is no larger than the heap work when k is at least 2 and is still linear when k is 1.
Space	O(k) extra	The heap stores at most one pointer from each non-empty list. The linked nodes are the required returned output, so their O(n) storage is excluded from extra space. The bound is O(min(k, n)) in the worst shape because no more than n non-empty lists can contribute a node.

Here n is the total number of values across all input arrays, and k is the number of input lists.

Annotated solutionC++ · heap frontier with a dummy result node

CPPBuild the linked lists, merge their current heads with a min-heap, and return the merged chain.

#include <queue>
#include <vector>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* mergeKLists(vector<vector<int>>& lists) {
        auto cmp = [](ListNode* a, ListNode* b) {
            return a->val > b->val;
        };

        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);

        for (auto& values : lists) {
            if (values.empty()) {
                continue;
            }

            ListNode* head = new ListNode(values[0]);
            ListNode* current = head;

            for (int i = 1; i < static_cast<int>(values.size()); ++i) {
                current->next = new ListNode(values[i]);
                current = current->next;
            }

            pq.push(head);
        }

        ListNode dummy;
        ListNode* tail = &dummy;

        while (!pq.empty()) {
            ListNode* node = pq.top();
            pq.pop();

            tail->next = node;
            tail = node;

            if (node->next != nullptr) {
                pq.push(node->next);
            }
        }

        return dummy.next;
    }
};

The comparator reverses the usual priority queue ordering: returning a->val > b->val makes the smallest value appear at the top. The line that pushes node->next after attaching node is the central invariant. It advances only the list that just contributed a value, while every other list remains represented by its existing heap node. No separate sorting pass is needed.

The pairwise alternativea different arrangement that trades the heap for repeated two-list merges

You can also merge the lists two at a time. Merge list 0 with list 1, list 2 with list 3, and so on; then merge those results in another round until one list remains. Each round touches every node once, and there are O(log k) rounds, giving O(n log k) time. Unlike the heap version, this approach does not maintain a heap of current heads.

CPPPair the lists and repeatedly merge adjacent pairs until only one sorted list remains.

#include <vector>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution {
private:
    ListNode* mergeTwo(ListNode* a, ListNode* b) {
        ListNode dummy;
        ListNode* tail = &dummy;

        while (a != nullptr && b != nullptr) {
            if (a->val <= b->val) {
                tail->next = a;
                a = a->next;
            } else {
                tail->next = b;
                b = b->next;
            }
            tail = tail->next;
        }

        tail->next = (a != nullptr) ? a : b;
        return dummy.next;
    }

public:
    ListNode* mergeKLists(vector<vector<int>>& lists) {
        vector<ListNode*> heads;

        for (auto& values : lists) {
            ListNode* head = nullptr;
            ListNode* tail = nullptr;

            for (int value : values) {
                ListNode* node = new ListNode(value);
                if (head == nullptr) {
                    head = node;
                } else {
                    tail->next = node;
                }
                tail = node;
            }

            heads.push_back(head);
        }

        while (heads.size() > 1) {
            vector<ListNode*> nextRound;

            for (int i = 0; i < static_cast<int>(heads.size()); i += 2) {
                ListNode* first = heads[i];
                ListNode* second = (i + 1 < static_cast<int>(heads.size()))
                    ? heads[i + 1]
                    : nullptr;
                nextRound.push_back(mergeTwo(first, second));
            }

            heads = move(nextRound);
        }

        return heads.empty() ? nullptr : heads[0];
    }
};

This is not asymptotically better than the heap solution: both take O(n log k) time, and pairwise merging uses O(k) pointer storage for the current round while the returned nodes remain output storage. It can be easier to reason about when you already have a reliable two-list merge, while the heap version is more direct when lists become available incrementally.