如何合并 K 个有序链表？为什么分治比逐个合并快？

简化版

分治两两配对合并：把 K 个有序链表两两合并成 K/2 个，再两两合并成 K/4 个……log K 轮后合成一个。设总节点数为 N，每一轮所有合并加起来都要扫 N 个节点，共 log K 轮，所以是 O(N log K)。而「用一条结果链依次去合并剩下每一条」是 O(N·K)，慢得多——因为前面的节点被反复扫描。也可以用最小堆达到同样的 O(N log K)。

详细版

ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    return merge(lists, 0, lists.length - 1);
}
// 分治：合并 lists[lo..hi]
ListNode merge(ListNode[] lists, int lo, int hi) {
    if (lo == hi) return lists[lo];
    int mid = lo + (hi - lo) / 2;
    ListNode l = merge(lists, lo, mid);       // 左半合成一条
    ListNode r = merge(lists, mid + 1, hi);   // 右半合成一条
    return mergeTwo(l, r);                     // 合并两条有序链表
}
// 合并两个有序链表，O(1) 额外空间
ListNode mergeTwo(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0), tail = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) { tail.next = a; a = a.next; }
        else                { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = (a != null) ? a : b;          // 接上剩余
    return dummy.next;
}

分治结构：把 K 条链表当成「区间」，递归对半分，底层合并两条。
复杂度：时间 O(N log K)，空间 O(log K)（递归栈；mergeTwo 本身 O(1)）。
对比：逐个合并 O(N·K)；最小堆 O(N log K)。

完整版教学

一、逐个合并为什么慢：重复扫描

最直觉的写法是：拿第 1 条当结果，去和第 2 条合并，再拿结果去和第 3 条合并……

问题出在结果链越来越长，却被一遍遍重新扫描。假设每条链有 n 个节点、共 k 条（总数 N=nk）：

合并第 1、2 条：扫 2n；
再合并第 3 条：结果已有 2n，扫 3n；
……合并第 k 条：扫 kn。

总代价 2n+3n+…+kn ≈ O(k²n) = O(k·N)。k 越大越亏，因为最早的那批节点被参与了近 k 次合并、反复搬运。

二、分治：两两配对，log K 轮

分治换个合并顺序，避免「一条长链反复被扫」：

第 1 轮：(L1,L2) (L3,L4) (L5,L6) (L7,L8)  →  4 条
第 2 轮：(L12,L34) (L56,L78)              →  2 条
第 3 轮：(L1234,L5678)                    →  1 条

每一轮把链表数量减半，所以只需 log₂K 轮就归成一条。关键差别是：分治里每个节点在每一轮只被搬运一次，不会像逐个合并那样被反复扫描。

三、每轮 O(N)、共 log K 轮 → O(N log K)

算总代价：

每一轮：这一轮的所有两两合并，加起来恰好把全部 N 个节点各处理一次，所以每轮是 O(N)（不管这一轮分成多少组，节点总数就是 N）。
轮数：每轮链表数减半，共 log₂K 轮。
合计：O(N) × log K = O(N log K)。

递归实现里没有「显式的轮」，但递归树的每一层深度对应一轮，效果一样：树高 log K，每层合并的节点总数 O(N)。

四、合并两个有序链表（O(1) 空间）

分治的底层操作是「合并两条有序链表」，这本身是道基础题：用一个哨兵头结点 dummy 和尾指针 tail，双指针比较两条链的头，把较小的接到 tail 后面，直到一条走完，再把另一条剩余部分整体接上。

链表合并的好处是不需要额外数组——只改指针（tail.next），空间 O(1)。这也是为什么归并思想在链表上特别合适（相比数组归并要 O(n) 辅助空间）。用 a.val <= b.val 取左边可保持稳定（相等节点原相对顺序不变）。

五、堆解法对比

另一种主流解法是最小堆（优先队列）：把 K 条链表的头结点都放进一个大小为 K 的小顶堆，每次弹出最小的接到结果后面，再把它的 next 入堆。

每个节点进出堆各一次，堆操作 O(log K)，共 N 个节点 → O(N log K)，和分治相同。
空间 O(K)（堆里最多 K 个节点）。

取舍：分治不需要额外数据结构、常数略小、递归栈 O(log K)；堆写法更直观、且适合数据流式地不断产生新元素的场景。两者渐进复杂度一致，面试都可作为标准答案，能说清「为什么都是 O(N log K)」是重点。

六、递归式、合并证明与数字推演

这道题的分治闭环是：每一轮把链表两两合并，所有节点只被扫描一次，链表数量约减半。递归调用只保证子问题正确，原问题能否正确仍取决于合并步骤是否覆盖所有情况且不重不漏。

总节点 N；每轮 Θ(N)，轮数 ceil(log₂K)，总 Θ(N log K)
递归树核对：每层子问题数 × 单个子问题的非递归代价

带数字推演：8 条各 100 节点的链表共 800 节点，分治 3 轮，每轮约扫描 800 个节点。推演时应记录每层输入规模、进入哪些子问题、合并新增了什么信息，不能只写最终答案。

记忆钩子：先写“分成什么、递归返回什么、怎样合并”，再列递推式；只会套主定理而说不清合并，说明算法还没有真正掌握。

七、实现代价、退化条件与替代方案

实现边界是：合并两个链表要保存 next 并正确接尾；K=0、空链表和大量空表都要处理。除了渐进时间，还要把递归栈、辅助数组、输入是否被修改以及最坏输入考虑进去。

检查项	面试中要回答的内容
基本情况	规模 0 或 1 时如何直接返回
规模缩小	每次递归是否严格靠近基本情况
合并正确性	子解怎样推出原问题答案
资源代价	递归深度、辅助结构与数据复制
退化保护	随机化、阈值切换、预排序或迭代改写

测试至少覆盖最小规模、奇偶长度、全部相等、严格有序/逆序、极端偏斜划分和会触发最大计数或溢出的数据。若存在更直接的线性算法、堆算法或动态规划，还要说明分治方案的教学价值与工程取舍。

八、常见误区与追问

误区：逐个合并也是 O(N log K)。 逐个加入会让已合并长链反复扫描，均长时可到 O(NK)。
误区：分治需要复制所有节点。 可原地重连 next，辅助递归/轮次空间 O(log K) 或 O(1)。
误区：每轮成本越来越大所以不是 O(N)。 链表数减少、单表变长，但该轮所有节点总数仍是 N。
追问：为什么堆解法也是 N log K？ 每个节点进行一次大小至多 K 的入堆/出堆。
追问：什么时候选堆？ 输入流式到达或希望随时取当前最小节点时。
追问：稳定性怎样定义？ 值相等时固定先取某一输入链，可保持输入内相对顺序。

九、加强记忆

合并 K 个有序链表用分治：两两配对合并，每轮减半，共 log K 轮；每轮把全部 N 个节点各处理一次 O(N) → 总 O(N log K)。它比「一条结果链依次合并剩余每条」的 O(N·K) 快，因为后者让早期节点被反复扫描。底层的「合并两条有序链表」用 dummy 头 + 双指针、只改指针、空间 O(1)。等价的最小堆解法也是 O(N log K)。

简化版

详细版