好的，我们这次来详细讲解 LeetCode 第 23 题：合并 K 个升序链表（Merge k Sorted Lists）。

这道题是合并两个有序链表的进阶版，是面试中非常高频的题目，它能很好地考察你对分治算法和堆（优先队列） 的理解和应用。

1. 题目描述

题目：
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，并返回这个链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个升序链表中得到：
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

2. 问题分析与思路萌芽

我们先从最简单的情况开始思考。

第一步：回顾基础——如何合并两个有序链表？
这是一个经典的算法，我们使用一个虚拟头节点（dummy node），然后比较两个链表当前节点的值，将较小的那个节点连接到新链表上，直到某个链表为空，再将另一个非空链表直接接上。

第二步：问题升级——现在有 K 个链表，怎么办？
最直观的想法是延伸“合并两个”的思路。我们可以：

1. 顺序合并：将第一个和第二个链表合并，得到一个新链表；再用这个新链表去和第三个链表合并；以此类推，直到合并完所有链表。
2. 分治合并：这是“顺序合并”的优化。我们不是一个个顺序合并，而是两两配对，同时合并，这样能大大减少合并的次数。
3. 使用最小堆（优先队列）：维护一个大小为 K 的最小堆，初始时将 所有链表的头节点 放入堆中。每次从堆中弹出最小的节点，连接到结果链表上，然后把这个最小节点所在链表的下一个节点（如果存在）加入堆中。

接下来，我们一步步深入讲解这三种方法，重点是分治法和最小堆法。

3. 方法一：顺序合并（思路简单但效率较低）

核心思想：将合并 k 个链表的问题，转化为执行 k-1 次“合并两个链表”的操作。

详细步骤：

1. 如果链表数组 lists 为空，直接返回 nullptr。
2. 初始化结果链表 ans 为 lists[0]。
3. 从 i = 1 开始遍历到 i = lists.size() - 1：
   • 将当前的结果链表 ans 与 lists[i] 进行合并（调用合并两个链表的函数）。
   • 将合并后的新链表赋值给 ans。
4. 返回最终的 ans。

时间复杂度分析：

• 假设每个链表的最长长度为 n。
• 第一次合并：ans 长度为 n，lists[1] 长度为 n，合并操作时间复杂度为 O(n + n) = O(2n)。
• 第二次合并：ans 长度变为 2n，与 lists[2] (长度为 n) 合并，时间复杂度为 O(3n)。
• ...
• 第 k-1 次合并：ans 长度约为 (k-1)n，与 lists[k-1] (长度为 n) 合并，时间复杂度为 O(kn)。
• 总时间复杂度为 O(2n + 3n + ... + kn) = O(n * (2+3+...+k)) = O(n * k²)。这是一个较高的复杂度。

代码示意（关键函数）：

// 合并两个链表的函数（基础）
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}

// 顺序合并的主函数
ListNode* mergeKLists(vector<ListNode*>& lists) {
    if (lists.empty()) return nullptr;
    ListNode* ans = lists[0];
    for (int i = 1; i < lists.size(); ++i) {
        ans = mergeTwoLists(ans, lists[i]);
    }
    return ans;
}

缺点：效率低，尤其是当 k 很大时。

4. 方法二：分治合并（效率高，推荐）

核心思想：模仿归并排序（Merge Sort）的思想。我们不是顺序合并，而是将 k 个链表两两配对，进行一轮合并；然后对合并后的新链表数组再次两两配对合并；重复这个过程，直到只剩下一个链表。

这个过程就像一个二叉树，从叶子节点（原始链表）开始，层层向上合并。

详细步骤：

1. 定义一个辅助函数 mergeKListsRange(lists, start, end)，表示合并 lists 中从下标 start 到 end 的链表。
2. 递归基（什么时候停止？）：
   • 如果 start > end，返回 nullptr。
   • 如果 start == end，说明范围内只有一个链表，直接返回 lists[start]。
3. 分解（如何缩小问题规模？）：
   • 计算中间位置 mid = start + (end - start) / 2。
   • 递归地合并左半部分 [start, mid]，得到链表 left。
   • 递归地合并右半部分 [mid + 1, end]，得到链表 right。
4. 合并：调用 mergeTwoLists(left, right)，将左右两个有序链表合并，返回最终结果。

时间复杂度分析：

• 第一轮合并：k 个链表被分成 k/2 组，每组两个链表合并，每组合并时间最多为 O(2n)，总时间 O(k/2 * 2n) = O(kn)。
• 第二轮合并：k/2 个新链表被分成 k/4 组，每组合并时间最多为 O(4n)，总时间 O(k/4 * 4n) = O(kn)。
• ...
• 总共有 logk 轮合并。
• 所以总时间复杂度为 O(kn * logk)。这比顺序合并的 O(k²n) 要好得多。

过程图示（以 k=4 为例）：

初始链表: L0, L1, L2, L3

第一层合并 (分治)：
  合并(L0, L1) -> 得到新链表M0
  合并(L2, L3) -> 得到新链表M1

第二层合并：
  合并(M0, M1) -> 得到最终结果链表

代码实现：

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }

private:
    // 分治函数
    ListNode* merge(vector<ListNode*>& lists, int left, int right) {
        // 1. 递归基
        if (left > right) return nullptr;
        if (left == right) return lists[left]; // 只有一个链表，直接返回

        // 2. 分解
        int mid = left + (right - left) / 2;
        ListNode* l1 = merge(lists, left, mid);
        ListNode* l2 = merge(lists, mid + 1, right);

        // 3. 合并
        return mergeTwoLists(l1, l2);
    }

    // 合并两个链表的辅助函数
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* tail = &dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }
        tail->next = l1 ? l1 : l2;
        return dummy.next;
    }
};

5. 方法三：使用最小堆（优先队列）（同样高效）

核心思想：维护一个当前所有链表头节点中的最小值。这正是一个最小堆（Min Heap） 或优先队列（Priority Queue） 的典型应用场景。

详细步骤：

1. 创建一个最小堆（C++ 中用 priority_queue，需要自定义比较规则，因为存储的是 ListNode*）。
2. 初始化：遍历所有链表，将每个链表的头节点（如果不为空）加入堆中。
3. 创建一个虚拟头节点 dummy 和一个尾指针 tail 指向它。
4. 循环，直到堆为空：
   a. 从堆中弹出值最小的节点（即堆顶），记为 minNode。
   b. 将 minNode 连接到 tail 的后面（即 tail->next = minNode）。
   c. tail 指针向后移动一位（tail = tail->next）。
   d. 检查 minNode 所在的链表是否还有下一个节点（即 minNode->next 是否为空）。如果不为空，则将 minNode->next 这个新节点加入堆中。
5. 循环结束后，返回 dummy.next。

为什么这样做？

• 堆始终保持了当前所有待比较节点中的最小值在堆顶。
• 每次我们取出最小值，并补充它所在链表的下一个节点，相当于 K 个指针在各自链表上依次前进。

时间复杂度分析：

• 堆的大小最大为 K。
• 我们总共会有 N（所有链表节点总数）次弹出操作和最多 N 次插入操作。
• 每次堆操作（插入或弹出）的时间复杂度是 O(logK)。
• 因此总时间复杂度为 O(N * logK)。

代码实现（C++）：

class Solution {
public:
    // 自定义比较函数，因为priority_queue默认是最大堆
    struct Compare {
        bool operator()(ListNode* a, ListNode* b) {
            return a->val > b->val; // 小顶堆是大于号
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 定义一个小顶堆（优先队列）
        priority_queue<ListNode*, vector<ListNode*>, Compare> minHeap;

        // 1. 初始化：将所有链表的头节点加入堆
        for (ListNode* list : lists) {
            if (list) { // 防止空链表
                minHeap.push(list);
            }
        }

        // 2. 创建虚拟头节点
        ListNode dummy(0);
        ListNode* tail = &dummy;

        // 3. 循环处理堆
        while (!minHeap.empty()) {
            // 取出当前最小的节点
            ListNode* minNode = minHeap.top();
            minHeap.pop();

            // 将该节点连接到结果链表
            tail->next = minNode;
            tail = tail->next;

            // 如果该节点所在链表还有下一个节点，则加入堆中
            if (minNode->next) {
                minHeap.push(minNode->next);
            }
        }

        return dummy.next;
    }
};

6. 总结与对比

如何选择？

• 面试中，如果能直接写出分治或最小堆方法，会是非常好的表现。
• 最小堆法思路更直观，更容易理解和讲述。
• 分治法的空间复杂度（递归栈）通常比堆法略优，且是经典的算法思想。

希望这个从基础到优化、循序渐进、细致入微的讲解能让你彻底理解这道经典的 LeetCode 题目！