好的，我们这次来详细讲解 LeetCode 第 23 题「合并 K 个升序链表」。

1. 题目描述

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

示例：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：将三个链表合并后得到一个新的有序链表。

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] 按升序排列
• 链表的总长度不超过 10^4

2. 题意理解

我们已知如何合并两个有序链表（第 21 题），但现在有 k 个有序链表。
最直接的想法是：

1. 先合并前两个链表，得到一个新链表。
2. 再将新链表与第三个链表合并，依此类推，直到合并完所有链表。

但这种方法效率较低：

• 假设每个链表长度都是 n，第一次合并：n + n = 2n，第二次合并：2n + n = 3n，……
• 总操作次数：n(2+3+...+k) ≈ O(k²n)，当 k 很大时很慢。

我们需要更高效的方法。

3. 思路分析

核心问题：每次从 k 个链表的当前头节点中选出最小的节点，接到结果链表中。

3.1 直接比较法（暴力选取最小）

每次比较 k 个链表的当前头节点，找出最小值，插入结果链表，并移动对应链表的指针。

• 一次选取最小值需要 O(k) 时间。
• 总节点数 N = k × n（最坏情况），总时间 O(kN)，若 k 大则慢。

3.2 使用优先队列（最小堆）优化选取最小值的过程

• 将 k 个链表的头节点加入最小堆（按节点值排序）。
• 每次从堆顶取出最小节点，插入结果链表，并将该节点的下一个节点加入堆。
• 堆的大小最大为 k，每次插入删除 O(log k)。
• 总节点数 N，总时间复杂度 O(N log k)。

3.3 分治法（两两合并）

• 将 k 个链表两两配对合并，第一轮合并后剩下 k/2 个链表，再继续合并，直到只剩一个链表。
• 每轮合并需要处理所有节点（总 N 个节点），合并轮数为 O(log k)，总时间复杂度 O(N log k)。
• 空间复杂度 O(1)（递归栈空间 O(log k) 或迭代 O(1)）。

4. 详细讲解：最小堆解法（常用且直观）

4.1 步骤

1. 创建一个小根堆（优先队列），存储节点，按节点的值排序。
2. 遍历 lists，将每个链表的头节点加入堆（如果非空）。
3. 初始化一个哑节点（dummy）作为合并后链表的头部的前驱。
4. 循环直到堆为空：
   • 弹出堆顶节点（当前最小节点）
   • 将该节点接到结果链表的尾部
   • 如果该节点有下一个节点，将下一个节点加入堆
5. 返回 dummy.next。

4.2 示例推演

lists = [[1,4,5],[1,3,4],[2,6]]

初始堆（加入各链表头）：
堆中：[1(链表1), 1(链表2), 2(链表3)]

循环：

1. 弹出 1(链表1)，结果链表：1，链表1 下一个是 4，入堆 → 堆：[1(链表2), 2(链表3), 4(链表1)]
2. 弹出 1(链表2)，结果链表：1→1，链表2 下一个是 3，入堆 → 堆：[2(链表3), 3(链表2), 4(链表1)]
3. 弹出 2(链表3)，结果链表：1→1→2，链表3 下一个是 6，入堆 → 堆：[3(链表2), 4(链表1), 6(链表3)]
4. 弹出 3(链表2)，结果链表：1→1→2→3，链表2 下一个是 4，入堆 → 堆：[4(链表1), 4(链表2), 6(链表3)]
5. 弹出 4(链表1)，结果链表：1→1→2→3→4，链表1 下一个是 5，入堆 → 堆：[4(链表2), 5(链表1), 6(链表3)]
6. 弹出 4(链表2)，结果链表：1→1→2→3→4→4，链表2 无下一个 → 堆：[5(链表1), 6(链表3)]
7. 弹出 5(链表1)，结果链表：1→1→2→3→4→4→5，链表1 无下一个 → 堆：[6(链表3)]
8. 弹出 6(链表3)，结果链表：1→1→2→3→4→4→5→6，链表3 无下一个 → 堆空，结束。

5. 代码实现（Python）

import heapq

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def mergeKLists(self, lists):
        # 最小堆
        heap = []
        # 初始化堆，加入每个链表的头节点
        for i, node in enumerate(lists):
            if node:
                heapq.heappush(heap, (node.val, i, node))
                # 这里加 i 是为了避免比较 node（ListNode 不支持比较），当 val 相同时按 i 排序
        
        dummy = ListNode(0)
        cur = dummy
        
        while heap:
            val, i, node = heapq.heappop(heap)
            cur.next = node
            cur = cur.next
            if node.next:
                heapq.heappush(heap, (node.next.val, i, node.next))
        
        return dummy.next

6. 复杂度分析

• 时间复杂度：O(N log k)，N 是总节点数，k 是链表个数。
• 空间复杂度：O(k)，堆的大小。

7. 分治法解法简介（对比）

分治法代码（递归两两合并，利用合并两个有序链表函数）：

class Solution:
    def mergeKLists(self, lists):
        if not lists:
            return None
        if len(lists) == 1:
            return lists[0]
        
        mid = len(lists) // 2
        left = self.mergeKLists(lists[:mid])
        right = self.mergeKLists(lists[mid:])
        return self.mergeTwoLists(left, right)
    
    def mergeTwoLists(self, l1, l2):
        dummy = cur = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        cur.next = l1 or l2
        return dummy.next

• 时间复杂度：O(N log k)
• 空间复杂度：O(log k)（递归栈）

8. 总结

• 暴力顺序合并：O(k²n) 慢，不推荐。
• 最小堆方法：O(N log k) 时间，O(k) 空间，直观常用。
• 分治法：O(N log k) 时间，O(log k) 空间（递归栈），效率高，代码简洁。

两种 O(N log k) 方法都是面试常考思路，建议都掌握。