23. 合并 K 个升序链表

难度：🔴 Hard | 标签：链表、堆、分治 | 状态：⬜ LeetCode 链接

思路

优先队列（小顶堆）：把每个链表头放进堆，每次弹出最小的接到结果，再把它的下一个推进堆。

也可分治两两合并，O(n log k) 同阶。

代码

class Solution {
public:
    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 (auto* h : lists) if (h) pq.push(h);
        ListNode dummy(0), *tail = &dummy;
        while (!pq.empty()) {
            auto* p = pq.top(); pq.pop();
            tail->next = p; tail = p;
            if (p->next) pq.push(p->next);
        }
        return dummy.next;
    }
};

复杂度

• 时间 O(N log k)，N 是总节点数
• 空间 O(k)

易错 / 回顾

• 比较函数 > 表示小顶堆（C++ 反着写）
• 入堆前判 nullptr，否则 deref 崩
• 两两合并 + 分治也是 O(N log k)，但实现细节更多