LeetCode LCR 078. 合并 K 个升序链表 | 走在修行的大街上

走在修行的大街上

2026-03-28 HGNULB 约 18 分钟

文章信息 5 个分类 5 个标签

分类

LeetCode 困难 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

目录

题目描述

✅ LCR 078. 合并 K 个升序链表

题意分析

输入是一个链表数组，数组里每条链表本身已经按升序排好，要求把它们合成一条升序链表并返回新的头节点。

把链表条数固定为 2，这就是第 21 题「合并两个有序链表」；本题是它从两条到 k 条的规模化版本，难度也从简单跳到了困难。多出来的那一层不在「怎么合并两条」，而在「同一时刻有 k 个来源，每一步该从谁那里取」——规模化把一个比较问题升级成了调度问题。

「每条链表本身已经升序」是全题唯一的题设条件，也是它区别于普通排序的地方。忽略这句话，把所有值收集起来排一遍序当然也能得到答案，但那意味着重新比较了大量早就确定了相对顺序的元素——题目被标为困难，考的正是怎么把这份已有的有序性用掉。

返回值是节点指针，题目也没要求保留输入结构，因此可以直接重接输入节点的指针，不必新建节点。这决定了合并过程的额外空间可以做到与节点总数无关。

需要单独想清楚的边界有四种：数组本身为空（长度 0），此时答案是空链表；数组非空但某些元素是空链表，它们不能参与后续比较，却也不能让流程崩掉；数组只有一个元素，答案就是它本身；所有元素都是空链表，答案仍是空。这四种里前两种最常被漏掉。

解法一：最小堆按头节点归并

核心思路

最朴素的做法是把所有节点的值倒进一个数组，排序后重新串成链表。它能过，时间是 $O(n \log n)$、空间 $O(n)$，但完全没有用到「每条链已经有序」这个条件。

瓶颈就在这里。既然每条链内部有序，那么下一个应该接入结果的节点，必然是各条链当前头节点中最小的那一个——理由是任何还没被合并的节点，要么就是它所在链的当前头节点，要么排在那个头节点后面因而不小于它。这意味着任一时刻真正需要参与比较的候选只有 k 个，而不是 n 个。整体排序之所以浪费，就是因为它把已知有序的元素也拿去互相比较了。

于是问题被改写成一个反复执行的原语：「在 k 个候选中取出最小的，然后用它的后继补位」。线性扫一遍候选是 $O(k)$，做 n 次就是 $O(nk)$；而小顶堆能把「取最小」和「插入新候选」都压到 $O(\log k)$，这正是堆最擅长的场景——极值查询要发生很多次，且集合在不断变化。

循环不变量是：每轮开始时，堆里恰好装着每条尚有剩余节点的链表的当前头节点，每条链最多贡献一个；结果链表已经按非降序接好了全局最小的若干个节点，tail 指向它的末尾。由上面那条观察，堆顶就是全体未合并节点的最小值。弹出堆顶接到 tail 之后，若它有后继就把后继入堆，那条链的候选被更新，不变量恰好恢复；堆为空等价于所有链都已耗尽，也就是合并完成。

不变量还附带一个容易被忽略的结论：循环退出时，最后弹出的那个节点必然没有后继——否则它的后继会被压进堆，堆就不会空。所以 tail.next 天然是空，不需要手动截断尾部。

解题步骤

建一个按节点值升序排列的小顶堆。为什么：本题要反复取最小值并插入新元素，这正是堆的适用判据；比较器只看 val，不涉及节点身份。

遍历链表数组，只把非空的头节点入堆。为什么：数组里允许存在空链表，它们没有候选值；Java 的 PriorityQueue 也不接受 null，不过滤会当场抛异常。

建哨兵节点 dummy 和尾指针 tail = dummy。为什么：结果链表的头节点在循环里才产生，有哨兵就不必为「第一个节点」写特殊分支；tail 让每次追加都是 $O(1)$。

循环直到堆空：弹出堆顶节点，令 tail.next = node 再把 tail 前移。为什么：由不变量，堆顶是全局未合并部分的最小值，直接追加就能保持结果非降序。

若弹出节点的后继非空，把后继入堆。为什么：这条链的候选必须被更新，否则该链剩下的节点永远进不了比较，会整段丢失。

堆空后返回 dummy.next。为什么：真正的头节点只有哨兵知道；此时 tail.next 已天然为空，无需额外置空。

以 lists = [[1,4,5],[1,3,4],[2,6]] 走一遍。 为了区分同值节点，把第一条链的节点记作 A1、A4、A5，第二条记作 B1、B3、B4，第三条记作 C2、C6。

初始化：三条链都非空，堆里是 {A1(1), B1(1), C2(2)}，tail = dummy。

第 1 轮：堆顶取值 1。这里 A1 与 B1 取值相同，堆不保证先弹哪一个，但因为两者的值一样，最终输出的值序列不受影响；这里设弹出 A1。接到结果尾部，结果为 1；A1 的后继 A4 入堆，堆变成 {B1(1), C2(2), A4(4)}。

第 2 轮：弹出 B1（值 1），结果为 1 → 1；B3 入堆，堆为 {C2(2), B3(3), A4(4)}。

第 3 轮：弹出 C2（值 2），结果为 1 → 1 → 2；C6 入堆，堆为 {B3(3), A4(4), C6(6)}。

第 4 轮：弹出 B3（值 3），结果为 1 → 1 → 2 → 3；B4 入堆，堆为 {A4(4), B4(4), C6(6)}。

第 5 轮：堆顶取值 4，同样存在并列，设弹出 A4，结果末尾追加 4；A5 入堆，堆为 {B4(4), A5(5), C6(6)}。

第 6 轮：弹出 B4（值 4），它的后继为空，不入堆，堆为 {A5(5), C6(6)}，结果为 1 → 1 → 2 → 3 → 4 → 4。

第 7 轮：弹出 A5（值 5），后继为空，堆为 {C6(6)}。

第 8 轮：弹出 C6（值 6），后继为空，堆变空，循环退出。最后弹出的 C6 本来就没有后继，所以 tail.next 是空。

返回 dummy.next，得到 [1,1,2,3,4,4,5,6]。

代码实现

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((first, second) -> Integer.compare(first.val, second.val));
        for (ListNode node : lists) {
            if (node != null) {
                minHeap.offer(node);
            }
        }

        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (!minHeap.isEmpty()) {
            // 堆顶就是当前所有链表头节点中最小的节点。
            ListNode node = minHeap.poll();
            tail.next = node;
            tail = tail.next;
            if (node.next != null) {
                minHeap.offer(node.next);
            }
        }

        return dummy.next;
    }
}

type ListNodeHeap []*ListNode

func (h ListNodeHeap) Len() int {
    return len(h)
}

func (h ListNodeHeap) Less(i int, j int) bool {
    return h[i].Val < h[j].Val
}

func (h ListNodeHeap) Swap(i int, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *ListNodeHeap) Push(x any) {
    *h = append(*h, x.(*ListNode))
}

func (h *ListNodeHeap) Pop() any {
    old := *h
    node := old[len(old)-1]
    *h = old[:len(old)-1]
    return node
}

func mergeKLists(lists []*ListNode) *ListNode {
    minHeap := &ListNodeHeap{}
    heap.Init(minHeap)
    for _, node := range lists {
        if node != nil {
            heap.Push(minHeap, node)
        }
    }

    dummy := &ListNode{}
    tail := dummy
    for minHeap.Len() > 0 {
        // 堆顶就是当前所有链表头节点中最小的节点。
        node := heap.Pop(minHeap).(*ListNode)
        tail.Next = node
        tail = tail.Next
        if node.Next != nil {
            heap.Push(minHeap, node.Next)
        }
    }

    return dummy.Next
}

复杂度分析

时间复杂度：$O(n \log k)$，n 为所有链表的节点总数，k 为链表条数。初始化最多把 k 个头节点入堆，代价 $O(k \log k)$；之后每个节点恰好出堆一次、入堆一次，而由不变量堆规模始终不超过 k，单次堆操作是 $O(\log k)$，这部分共 $O(n \log k)$。由于 k <= n，后一项是主导项。

空间复杂度：$O(k)$。堆里最多同时存 k 个节点，因为每条链任一时刻只贡献一个候选；除此之外只有哨兵和尾指针两个常数级变量。结果链表直接复用输入节点、没有新建任何节点，因此不额外计入。

关键点总结

多路归并的核心是先识别出「候选集只有 k 个」：每条有序数据源在同一时刻只有它的当前头部有资格竞争。凡是「多个已排序的源要合成一个」的问题都是这个骨架，外部排序和 LSM 树的 compaction 用的也是它。

「反复取极值 + 不断插入新元素」是选堆的判据。如果极值只取一次，或者集合从头到尾不变，排序或一次线性扫描更划算——不要看到「最小」就上堆。

堆里存的必须是节点（或能定位来源的索引），不能只存值。存值就丢掉了「它属于哪条链、后面还有什么」，候选集补位这一步就无从实现。

整数比较器写 Integer.compare(a, b) 而不是 a - b。当两个值相距超过 int 表示范围时相减会溢出、符号翻转，堆序性质被悄悄破坏；这条在任何用减法充当比较器的地方都成立。

面试视角：开口按「每条链有序 ⇒ 候选只有 k 个 ⇒ 用小顶堆」这条链推导，这是最容易讲清楚的路径；接着补一句「也可以两两分治归并，量级相同、空间更省」。常见追问是「为什么是 $\log k$ 而不是 $\log n$」和「链表是流式产生的怎么办」。把所有值收集起来排序再重建链表不能当主答案——它把有序性这个唯一的题设浪费掉了，等于把困难题降级成了排序练习。

解法二：分治归并链表

核心思路

换一个角度：合并两条有序链表是一个已经解决的问题（第 21 题），代价是两条链长度之和。那么合并 k 条最直接的复用方式是顺序累积——先把第一条和第二条合并，结果再和第三条合并，依此类推。

瓶颈在于这样做很不划算。第 i 次合并要重新遍历前面已经合并好的全部节点，如果每条链长为 m，总代价是 m + 2m + 3m + ... + km，量级为 $O(nk)$。同一个节点被反复搬运了最多 k 次。

关键观察是：一个节点被搬运的次数，等于它在「合并树」上从叶子走到根经过的合并次数。 顺序累积形成的是一棵深度为 k 的退化树，所以有节点被搬 k 次；改成两两配对、层层向上，合并树就变成平衡二叉树，深度降到 $O(\log k)$，每个节点最多被搬运这么多次。这正是归并排序的思路，只不过被归并的单位从「单个元素」升级成了「整条有序链表」。

递归的后置条件是：mergeRange(lists, left, right) 返回一条恰好包含 lists[left..right] 中全部节点、且升序排列的链表。 边界情形 left == right 时直接返回 lists[left]，它本身已升序（也允许是空链表）；否则把区间从中点劈成两段，各自递归得到一条有序链，再用两路归并缝成一条。整体正确性只需这两处各自成立，不必在脑子里展开整棵递归树。

两路归并自身的不变量是：每一步只从两条链的当前头节点中挑更小的接到 tail 之后，因此结果链始终非降序，且 tail 之后待处理的部分仍是两条有序链。 循环条件写「两者都非空」，退出后把还剩下的那一整段直接挂到 tail 后面——链表在这里比数组占便宜，剩余部分不需要逐个拷贝。这个写法顺带处理了输入本身就是空链表的情况：循环一次都不进，直接把非空的那条整体挂上。

比较用 <= 而不是 <，意味着值相等时优先取 first，归并是稳定的。本题只要求值有序，看不出差别，但把这套模板搬到「按某个字段排序对象」的场景时，稳定性是必需的。

解题步骤

先判断 lists.length == 0 并返回空。为什么：后面要用 lists.length - 1 作为右端点，空数组会得到 -1，递归里会去访问 lists[0] 而越界。

调用 mergeRange(lists, 0, lists.length - 1)。为什么：用左右闭区间表示「待合并的链表编号范围」，比传子数组省去拷贝。

递归边界：left == right 时返回 lists[left]。为什么：单条链本身就满足后置条件；它可能是空链表，交给归并去消化，不必在这里特判。

用 mid = left + (right - left) / 2 劈分区间，分别递归左右两半。为什么：对半分才能让合并树平衡、深度是 $O(\log k)$；这个写法同时避开了 left + right 相加溢出的隐患。

把两个递归结果交给 mergeTwoLists。为什么：两半各自已经有序，问题被归约成已解决的两路归并。

mergeTwoLists 里建哨兵和尾指针，循环条件是两条链都非空，每轮取值更小的那个接上并前移对应指针。为什么：哨兵免掉首节点特判；只在都非空时循环，退出条件就变得非常明确。

循环退出后，把非空的那条链整段挂到 tail 之后。为什么：剩余部分本身已有序且全都不小于已输出的节点，整体挂接即可，逐个搬运是白做功。

返回 dummy.next。

以 lists = [[1,4,5],[1,3,4],[2,6]] 走一遍。 数组长度 3，调用 mergeRange(0, 2)。

mergeRange(0, 2)：mid = 0 + (2 - 0) / 2 = 1，于是左半是 mergeRange(0, 1)，右半是 mergeRange(2, 2)。

先算 mergeRange(0, 1)：mid = 0，左半 mergeRange(0, 0) 返回 [1,4,5]，右半 mergeRange(1, 1) 返回 [1,3,4]。两路归并的过程是——比 1 与 1，1 <= 1 取第一条的 1；比 4 与 1，取第二条的 1；比 4 与 3，取 3；比 4 与 4，4 <= 4 取第一条的 4；比 5 与 4，取第二条的 4，此时第二条耗尽，循环退出，把第一条剩下的 [5] 整段挂上。结果是 [1,1,3,4,4,5]。

再算 mergeRange(2, 2)，直接返回 [2,6]。

最后归并 [1,1,3,4,4,5] 与 [2,6]：比 1 与 2 取 1；比 1 与 2 取 1；比 3 与 2 取 2；比 3 与 6 取 3；比 4 与 6 取 4；比 4 与 6 取 4；比 5 与 6 取 5，此时第一条耗尽，循环退出，把第二条剩下的 [6] 整段挂上。

最终返回 [1,1,2,3,4,4,5,6]，与解法一结果一致。整个过程递归树只有两层归并，每层各处理 8 个节点。

代码实现

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }

        return mergeRange(lists, 0, lists.length - 1);
    }

    private ListNode mergeRange(ListNode[] lists, int left, int right) {
        if (left == right) {
            return lists[left];
        }

        int mid = left + (right - left) / 2;
        ListNode first = mergeRange(lists, left, mid);
        ListNode second = mergeRange(lists, mid + 1, right);
        return mergeTwoLists(first, second);
    }

    private ListNode mergeTwoLists(ListNode first, ListNode second) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        while (first != null && second != null) {
            // 每次只接入两条链表当前头节点中更小的那个。
            if (first.val <= second.val) {
                tail.next = first;
                first = first.next;
            } else {
                tail.next = second;
                second = second.next;
            }
            tail = tail.next;
        }

        if (first != null) {
            tail.next = first;
        } else {
            tail.next = second;
        }
        return dummy.next;
    }
}

func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    }

    return mergeRange(lists, 0, len(lists)-1)
}

func mergeRange(lists []*ListNode, left int, right int) *ListNode {
    if left == right {
        return lists[left]
    }

    mid := left + (right-left)/2
    first := mergeRange(lists, left, mid)
    second := mergeRange(lists, mid+1, right)
    return mergeTwoLists(first, second)
}

func mergeTwoLists(first *ListNode, second *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy

    for first != nil && second != nil {
        // 每次只接入两条链表当前头节点中更小的那个。
        if first.Val <= second.Val {
            tail.Next = first
            first = first.Next
        } else {
            tail.Next = second
            second = second.Next
        }
        tail = tail.Next
    }

    if first != nil {
        tail.Next = first
    } else {
        tail.Next = second
    }

    return dummy.Next
}

复杂度分析

时间复杂度：$O(n \log k)$。递归树的高度是 $\lceil \log_2 k \rceil$，而同一层上的各次归并处理的是互不相交的节点集合，加起来恰好是全部 n 个节点各一次常数级比较和指针挂接。所以总代价等于层数乘以每层的 n。这里对数的底数对应的是链表条数 k，因为被对半划分的是数组而不是节点。

空间复杂度：$O(\log k)$。唯一的额外开销是递归栈，深度等于递归树高度，每帧只存 mid、first、second 等常数个变量；归并全程是原地重接指针，没有新建节点。返回链表不计入额外空间。

关键点总结

归并的对象可以是任何「已经排好序的整体」，不必是单个元素。一旦识别出可归并单元是什么，归并排序的骨架就能整体搬过来。

顺序累积和两两配对的差别只是合并树的形状：前者退化成深度 k 的链，后者是深度 $\log k$ 的平衡树。凡是反复做两两合并的场景（合并文件、拼接字符串、Huffman 编码），都要先问一句「合并顺序会不会影响总代价」。

分治的正确性用后置条件表述最省力：断言「返回区间内所有元素构成的有序序列」，然后只验证边界与合并两处，不需要在脑子里展开整棵递归树。

两路归并写成「循环处理两者都非空的部分，退出后把剩下的一整段直接挂上」，比一路搬到底更短也更难写错。链表比数组占便宜的地方正是剩余段不需要拷贝。

面试视角：这是堆之外必须能说出的第二条路，尤其当面试官追问「不用额外数据结构呢」。它还有个隐藏优势——被问到「怎么并行」时，分治天然可以把左右两半交给不同线程，而堆是串行瓶颈。用「一条一条累积合并」当主答案会立刻被追问复杂度，那个写法在 k 较大时退化到 $O(nk)$。

解法对比

两者的时间量级相同，真正的差别在于「维护什么」和额外空间。堆解法维护的是一个当前候选集，这是标准的流式多路归并框架——数据可以边产生边处理，甚至不要求一开始就掌握全部链表；分治解法维护的是一棵合并树，必须先握有全部 k 条链才能划分区间，但它只用递归栈，额外空间更省，而且天然可并行。

面试里从堆讲起更顺：「每条链有序，所以候选只有 k 个」这一句话就把题意直接翻译成了数据结构选择，几乎不需要额外推导。分治则要多解释一步「为什么两两配对比顺序累积快」，讲不到合并树的深度就说不清。

选型的实际依据是数据形态：链表条数固定且能全部驻留内存时两者都可以，分治的常数更小；链表是流式产生的、或者 k 很大而每条很短时，堆更合适；反过来单条极长而 k 只有二三条时，直接顺序合并最简单，此时分治和堆都属于过度设计。

易错点总结

不过滤空链表就往堆里放：lists = [[],[1]] 时 minHeap.offer(null) 当场抛出空指针异常；即使换成允许存 null 的容器，比较器读 first.val 时同样会炸。

弹出堆顶后忘记把它的后继入堆：候选集只剩初始那批，lists = [[1,4,5],[1,3,4],[2,6]] 只会输出三个头节点，得到长度 3 的 [1,1,2] 而不是完整的 8 个节点。

比较器写成 first.val - second.val：当一条链含 -2147483648、另一条含 2147483647 时相减溢出、符号翻转，堆顶不再是最小值，输出的链表不再有序。

不用哨兵节点、直接拿 tail 拼接：tail 初始为空，第一次执行 tail.next = node 就抛空指针异常，lists = [[1]] 即可触发。

把每条链的所有节点一次性全部压进堆：lists 总长 n 时堆规模从 k 涨到 n，时间退化为 $O(n \log n)$、空间退化为 $O(n)$；结果虽然对，但等于放弃了「候选只有 k 个」这个核心结论。

分治写法不先处理 lists.length == 0：mergeRange(lists, 0, -1) 中 left == right 不成立，mid 算得 0，随后 mergeRange(lists, 0, 0) 去读 lists[0]，抛出数组下标越界。

mergeTwoLists 循环退出后忘记挂上剩余那一段：mergeTwoLists([1,4,5], [2]) 会返回 [1,2]，节点 4 和 5 整段丢失。

mergeTwoLists 的比较写成 first.val < second.val：值相等时优先取 second，归并不再稳定。本题的输出值序列看不出差别，但把这套模板用于「按字段排序对象、要求保持原相对顺序」时会给出错误顺序。

中点写成 (left + right) / 2：本题的链表条数规模不会触发问题，但一旦这套分治模板被搬到 left + right 可能超出 int 范围的场合，相加溢出为负数会让 lists[mid] 越界；改成 left + (right - left) / 2 没有任何成本。

相似题目

题目	难度	考察点
21. 合并两个有序链表	简单	只有两条链，是本题的归并原语，不涉及候选集调度与合并顺序
88. 合并两个有序数组	简单	载体换成数组，因为能随机访问，可以从后往前填，做到不占额外空间
148. 排序链表	中等	对单条无序链表做归并排序，多了「快慢指针找中点并断链」这一步
373. 查找和最小的 K 对数字	中等	候选来自两个数组的下标组合而非链表，入堆时要去重，避免同一对被压两次
632. 最小区间	困难	同样多路推进 `k` 条有序表，但要维护候选集内的最大值，求覆盖所有表的最小区间
剑指 Offer 25. 合并两个排序的链表	简单	与 21 同题换皮，常被额外要求给出递归版的两路归并
滴滴面试题-合并 k 个排序数组	中等	数据源换成数组，堆里必须存「数组下标 + 元素下标」二元组，节点不自带后继指针