你好！我是你的 OI 教练。今天我们要挑战链表专题中的“大山”——合并 K 个升序链表。

这道题是链表合并、堆（优先队列）以及分治思想的综合体现。在 NOI 竞赛中，这种“多路归并”的思想广泛应用于外排序、贪心策略以及复杂数据结构的维护中。

一、 预备知识点 checklist

1. 链表基础：指针操作、哨兵节点（Dummy Node）。
2. 优先队列（Heap）：掌握 std::priority_queue 的自定义比较函数。
3. 分治法（Divide and Conquer）：理解如何将大问题拆分为两个小规模的相同问题。
4. 复杂度分析：对比 $O(NK)$ 与 $O(N \log K)$ 的性能差异。

二、 题目描述：合并 K 个升序链表 (Merge k Sorted Lists)

题目背景： 在处理大规模海量数据时，我们经常需要将多个已经排好序的小文件合并成一个大文件。本题模拟了这一过程：给定 $k$ 个已经按升序排列的链表，请将它们合并成一个升序链表。

输入格式 (Standard Input)：

• 第一行包含一个整数 $k$，表示链表的数量。
• 接下来 $k$ 行，每行描述一个链表：
  • 每行第一个整数 $n_i$ 表示该链表的长度。
  • 随后跟随 $n_i$ 个整数，表示链表中的元素。

输出格式 (Standard Output)：

• 输出一行，包含合并后新链表的所有元素，整数之间以空格分隔。

输入样例 1：

3
3 1 4 5
3 1 3 4
2 2 6

输出样例 1：

1 1 2 3 4 4 5 6

输入样例 2：

0

输出样例 2：

(空)

数据规模与约定：

• $k \le 10^4$
• 链表总节点数 $N \le 10^4$
• $-10^4 \le \text{节点值} \le 10^4$
• 每个链表保证为升序。
• 时间限制：1.0s
• 内存限制：128MB

三、 教练的草稿纸：启发式推理过程

1. 暴力思路：两两合并

我们可以先合并前两个链表，得到的结果再和第三个合并……

• 思考：如果有 $k$ 个链表，总节点数为 $N$。第一次合并耗时约 $2N/k$，第二次 $3N/k$……最后一次 $N$。
• 复杂度：大约是 $O(N \times k)$。当 $k=10^4, N=10^4$ 时，运算量达到 $10^8$，在 1s 内非常危险。

2. 优化思路 A：优先队列（多路归并）

想象 $k$ 个链表排成一排，我们每次只需要看这 $k$ 个链表的“队头”。

• 步骤：
  1. 把所有链表的头节点放入一个“最小堆”。
  2. 弹出堆顶（当前全局最小），接入结果链表。
  3. 如果弹出的节点还有下一个节点，就把下一个节点放入堆。
• 复杂度：堆的大小始终为 $k$，每次操作 $\log k$。总复杂度 $O(N \log k)$。

3. 优化思路 B：分治合并

类似归并排序（Merge Sort）：

• 步骤：把 $k$ 个链表从中间切开，左边 $k/2$ 个合并成一个，右边 $k/2$ 个合并成一个，最后把这两个大链表合并。
• 复杂度：层数 $\log k$，每层处理 $N$ 个节点。总复杂度 $O(N \log k)$。

四、 算法流程图 (Mermaid 风格)

这里我们使用**优先队列（最小堆）**的方法进行推理：

graph TD
    Start("开始合并") --> CheckK{"K 等于 0 吗?"}
    CheckK -- "是" --> ReturnEmpty("返回空")
    CheckK -- "否" --> InitHeap("初始化最小堆 Priority Queue")
    
    InitHeap --> FillHeap("将 K 个链表的非空头节点存入堆")
    FillHeap --> CreateDummy("创建 Dummy 哨兵节点")
    CreateDummy --> SetTail("指针 Tail 指向 Dummy")
    
    SetTail --> Loop{"堆是否为空?"}
    Loop -- "否" --> PopHeap("弹出堆顶节点 Node")
    PopHeap --> Link("Tail 的 Next 指向 Node")
    Link --> MoveTail("Tail 指针后移")
    
    MoveTail --> HasNext{"Node 是否有下一个节点?"}
    HasNext -- "是" --> PushNext("将 Node 的 Next 放入堆")
    HasNext -- "否" --> Loop
    PushNext --> Loop
    
    Loop -- "是" --> Final("返回 Dummy 的 Next 节点")
    Final --> End("结束")

五、 时间与空间复杂度分析

• 时间复杂度分析：

  • 堆操作：总共有 $N$ 个节点，每个节点进出堆各一次。每次堆操作的时间是 $O(\log k)$。
  • 结论：总时间复杂度为 $O(N \log k)$。相比暴力法，在大数据量下有质的提升。

• 空间复杂度分析：

  • 优先队列：堆中最多同时存在 $k$ 个节点，空间 $O(k)$。
  • 结果链表：如果是原地修改指针，不需要额外空间；如果是新建节点，空间 $O(N)$。
  • 结论：在 NOI 竞赛中，我们通常修改指针，额外空间复杂度为 $O(k)$。

六、 读题关键词与坑点总结

1. “K 个”：
   • 当看到多个序列合并时，第一反应应是堆或分治。
2. “升序”：
   • 这是使用堆顶元素的依据。如果序列无序，必须先排序。
3. 内存限制与空指针：
   • 坑点 1：输入 $k=0$ 或输入了 $k$ 个空链表（例如 3 0 0 0）。
   • 坑点 2：priority_queue 默认是大根堆，合并升序链表需要小根堆，重载比较运算符时，a.val > b.val 才是小根堆。
4. NOI 技巧：
   • 如果 $k$ 很大但 $N$ 很小，分治和堆的效率相近。但如果内存极度受限（如 16MB），分治法（递归实现）可能会因为系统栈消耗更多内存，此时迭代式的堆操作更安全。

教练寄语：

这道题是“空间换时间”和“数据结构优化”的范例。记住：当你在 $k$ 个候选项中反复寻找极值时，堆就是你的最佳武器！