跳到主要内容

LeetCode 23. 合并 K 个升序链表

本节目标

用小根堆维护每条链表当前的头部候选，将合并两个有序链表推广到多路归并。

这道题是数据结构综合应用框架中的拓展题。它把链表操作与小根堆结合起来：链表提供有序的后继关系，堆负责在多条链表的当前候选中选出最小值。

查看原题

题意与约束​

给定一个链表数组，每条链表都按升序排列。请把所有节点合并为一条升序链表并返回头节点。数组中可能包含空链表，不同链表中也可能出现相同数值。

如果只有两条链表，可以用两个指针比较当前节点；当链表数量扩展到 k 条时，核心问题变成：如何高效找出 k 个当前头节点中的最小者。

从两路归并到多路归并​

任意时刻，每条尚未耗尽的链表只有头部节点可能成为全局下一个节点。因为链表内部有序，头部之后的节点不可能越过自己的头部提前被选择。

因此，小根堆中不需要放入全部节点，只需要放入每条非空链表当前尚未处理的第一个节点：

  1. 初始化时，把每条非空链表的头节点加入堆；
  2. 弹出值最小的节点，把它接到结果链表末尾；
  3. 若该节点还有后继，就把后继加入堆；
  4. 重复直到堆为空。

核心不变量​

每轮开始时，堆中恰好保存每条未耗尽链表的最小未处理节点。因此：

  • 堆顶一定是所有未处理节点中的全局最小值；
  • 弹出堆顶不会破坏结果链表的升序；
  • 只需补入同一条链表的后继，就能恢复不变量。

堆大小最多为 k，而不是所有节点总数。这正是利用各链表内部有序性减少候选数量的关键。

相同节点值如何比较​

不同链表的当前节点可能具有相同的 val。C++ 的比较器只按节点值确定优先级，相等时任意一个先出堆都不影响结果。

Python 的堆会在元组第一项相等时继续比较下一项，而两个 ListNode 对象本身不可比较。因此实现中加入递增序号，保存 (节点值, 序号, 节点)。序号只负责打破平局，不改变算法含义。

代码实现​

两份代码都复用原链表节点，不新建每个结果节点；哑节点只用于统一处理结果链表头部。堆里始终只有各链表的当前头部候选。

C++17
#include <queue>
#include <vector>
using namespace std;

class Solution {
private:
    struct CompareNode {
        bool operator()(ListNode* left, ListNode* right) const {
            return left->val > right->val;
        }
    };

public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, CompareNode> candidates;
        for (ListNode* head : lists) {
            if (head != nullptr) {
                candidates.push(head);
            }
        }

        ListNode dummy(0);
        ListNode* tail = &dummy;
        while (!candidates.empty()) {
            ListNode* node = candidates.top();
            candidates.pop();
            tail->next = node;
            tail = node;
            if (node->next != nullptr) {
                candidates.push(node->next);
            }
        }
        return dummy.next;
    }
};

复杂度分析​

设所有链表共有 n 个节点，链表数量为 k。

  • 时间复杂度：O(n log k)。每个节点恰好入堆、出堆各一次，堆大小不超过 k。
  • 空间复杂度：O(k)。不计返回链表本身，额外空间主要来自堆。

易错点​

  • 把所有节点一次性放入堆，虽然可行，但空间增至 O(n)，没有利用链表有序性。
  • 弹出节点后忘记把它的后继加入堆，导致该链表剩余部分丢失。
  • 把空链表头节点加入堆，造成空指针访问。
  • Python 直接保存 (node.val, node)，遇到相同值时会尝试比较节点对象并报错。
  • 接入结果链表时额外复制大量节点，增加不必要的实现复杂度。

模式迁移​

“每一路只暴露一个当前候选”的多路归并思想同样适用于：

  • 合并多个有序数组或文件；
  • 从多个有序序列中寻找第 k 小元素；
  • 外部排序中合并多个已排序数据块。

判断能否使用该模式的关键是：每一路内部是否有序，以及选走当前元素后，能否立刻得到这一路唯一的新候选。