news 2026/9/18 21:29:20

合并 K 个有序链表（Merge K Sorted Linked Lists）六种解法全解析：从暴力收集到堆与分治的渐进优化

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
合并 K 个有序链表（Merge K Sorted Linked Lists）六种解法全解析：从暴力收集到堆与分治的渐进优化

合并 K 个有序链表（Merge K Sorted Linked Lists）六种解法全解析：从暴力收集到堆与分治的渐进优化

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本文以 LeetCode 第 23 题「合并 K 个有序链表」为核心，完整梳理暴力收集排序、每轮扫描取最小、逐个两两合并、最小堆、递归分治与迭代分治共六种解法，给出多语言可运行实现，并结合本仓库（LeetCode solutions / NeetCode 题解库）中 14 种语言的源码文件与官方提示文件，剖析每种方案的复杂度成因与适用场景。读完本文，你将掌握如何在链表场景中灵活运用排序、优先队列与分治思想，并能对照仓库源码独立写出面试级解法。

前置知识（Prerequisites）

在开始攻克本题之前，建议先熟练掌握以下基础，它们被反复用于后续所有解法：

  • 链表（Linked Lists）：理解单向链表的结构、遍历方式与节点操作（dummy 头节点技巧、指针推进）。
  • 合并两个有序链表（Merge Two Sorted Lists）：这是所有高级解法中最核心的基本操作，本仓库对应的题解文档见 articles/merge-two-sorted-linked-lists.md。
  • 最小堆 / 优先队列（Min Heap / Priority Queue）：用于在 k 个链表中高效地找出当前最小元素。
  • 分治（Divide and Conquer）：像归并排序一样递归地两两拆分、两两合并的策略。
  • 排序（Sorting）：暴力解法中用于对所有收集到的值进行排序。

官方提示文件 hints/merge-k-sorted-linked-lists.md 给出的推荐目标为：时间复杂度和空间复杂度至少达到O(n * k)时间 /O(1)空间（其中k为链表数量，n为所有链表节点总数），并提示可以复用「合并两个有序链表」的思路，从i = 1开始依次执行mergeTwoLists(lists[i], lists[i - 1])并回写结果。下面六种解法将逐步逼近并超越这一目标。

问题与六种解法总览

给定k个已排序的链表头节点数组lists，要求将它们合并为一个完整的有序链表并返回其头节点。以经典用例lists = [[1,4,5],[1,3,4],[2,6]]为例，合并结果为[1,1,2,3,4,4,5,6]。

解法思路时间复杂度空间复杂度适用评价
1. 暴力收集排序忽略链表结构，收集全部值后排序重建$O(n \log n)$$O(n)$实现最简单，但排序主导开销
2. 每轮扫描取最小每次线性扫描 k 个头节点取最小值$O(n \cdot k)$$O(1)$无需额外空间，但扫描开销大
3. 逐个两两合并用合并两个链表的例程依次累积$O(n \cdot k)$$O(1)$逻辑清晰，适合少量链表
4. 最小堆用优先队列维护 k 个候选头节点$O(n \log k)$$O(k)$面试推荐解法，兼顾时间与空间
5. 分治（递归）二分区间递归合并左右两半$O(n \log k)$$O(\log k)$结构优雅，无额外堆空间
6. 分治（迭代）每轮两两配对合并，直到剩一条$O(n \log k)$$O(k)$（中间结果数组）无递归栈，工程上最常用

其中 $k$ 为链表总条数，$n$ 为所有链表节点总数。下面逐一展开。

1. 暴力解法（Brute Force）：收集、排序、重建

思路

最简单的做法是完全忽略链表的链式结构：遍历所有链表，把每个节点的值收集到一个数组中，整体排序后，再按顺序重建一条全新的有序链表。它没有任何"聪明"的合并逻辑，纯粹是收集 + 排序。

算法步骤

  1. 创建空数组nodes。
  2. 遍历每一条链表，把每个节点的值依次追加到nodes。
  3. 对nodes进行升序排序。
  4. 用 dummy 头节点重建链表：依次为每个值创建新节点并串接。
  5. 返回新链表的头节点。

参考实现（Python）

# 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: List[Optional[ListNode]]) -> Optional[ListNode]: nodes = [] for lst in lists: while lst: nodes.append(lst.val) lst = lst.next nodes.sort() res = ListNode(0) cur = res for node in nodes: cur.next = ListNode(node) cur = cur.next return res.next

复杂度分析

  • 时间复杂度：$O(n \log n)$，瓶颈是整体排序。
  • 空间复杂度：$O(n)$，需要存储全部节点值的数组以及重建的新链表。

实现点评

  • 优点：代码量最小、不易出错，适合快速验证正确性。
  • 缺点：完全抛弃了"每条链表本身已有序"这一关键信息，排序开销与额外空间都较大，且新建节点意味着内存翻倍。因此它通常只作为 baseline 存在。

2. 迭代法（Iteration）：每轮扫描 k 个头节点

思路

反复在所有链表的头节点中挑选值最小的那一个，接到结果链表的尾部，并把该链表的指针向后移动一位。这与"合并 k 个有序数组时每次取最小可用元素"的思路完全一致。

算法步骤

  1. 创建 dummy 节点，cur指向 dummy，用于构建结果链表。
  2. 循环执行：
    • 扫描所有链表，找出当前头节点值最小的链表下标minNode。
    • 若所有链表都为空（minNode == -1），终止循环。
    • 将该最小节点接到cur.next，cur前移。
    • 将该链表的头指针前移到下一个节点。
  3. 返回dummy.next。

参考实现（Python）

# 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: List[Optional[ListNode]]) -> Optional[ListNode]: res = ListNode(0) cur = res while True: minNode = -1 for i in range(len(lists)): if not lists[i]: continue if minNode == -1 or lists[minNode].val > lists[i].val: minNode = i if minNode == -1: break cur.next = lists[minNode] lists[minNode] = lists[minNode].next cur = cur.next return res.next

复杂度分析

  • 时间复杂度：$O(n \cdot k)$。每次选出最小值都要线性扫描 k 个头节点，共需选出 n 个节点。
  • 空间复杂度：$O(1)$。全程只复用原有节点，不创建新节点（仅一个 dummy）。

其中 $k$ 为链表总条数，$n$ 为所有链表节点总数。

实现点评

  • 优点：空间开销为零，直接在原节点上重组，思路直观。
  • 缺点：当 $k$ 较大时，每轮 $O(k)$ 的线性扫描代价过高。这正是解法 4（堆）要优化的地方——把"线性找最小"升级为"对数级取最小"。

3. 逐一两两合并（Merge Lists One By One）

思路

不一次性合并所有链表，而是一条一条地累积合并：

  • 先把链表0与链表1合并成一条有序链表；
  • 再把结果与链表2合并；
  • 再与链表3合并……直到全部合并完。

每一步的合并都复用标准的「合并两个有序链表」例程：比较两个头节点，接上较小的，推进对应指针，直到某一链表为空后把剩余部分整体接上。

算法步骤

  1. 若lists为空，返回null。
  2. 从下标1到k - 1循环：
    • 用mergeList(lists[i - 1], lists[i])合并两条链表；
    • 把合并结果存回lists[i]。
  3. 循环结束后，lists[k - 1]即为完整合并结果，返回它。

mergeList(l1, l2)例程：

  1. 创建 dummy 节点与tail指针。
  2. 当l1、l2均非空时：比较l1.val与l2.val，把较小者接到tail.next，推进对应链表指针与tail。
  3. 若某条链表仍有剩余节点，整体接到tail.next。
  4. 返回dummy.next。

参考实现（Python）

# 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: List[Optional[ListNode]]) -> Optional[ListNode]: if len(lists) == 0: return None for i in range(1, len(lists)): lists[i] = self.mergeList(lists[i - 1], lists[i]) return lists[-1] def mergeList(self, l1, l2): dummy = ListNode() tail = dummy while l1 and l2: if l1.val < l2.val: tail.next = l1 l1 = l1.next else: tail.next = l2 l2 = l2.next tail = tail.next if l1: tail.next = l1 if l2: tail.next = l2 return dummy.next

复杂度分析

  • 时间复杂度：$O(n \cdot k)$。第 $i$ 轮合并的链表长度约为 $(i+1) \cdot (n/k)$，总工作量约为 $\frac{n}{k} \sum_{i=1}^{k} i = O(nk)$。
  • 空间复杂度：$O(1)$（不含输入存储）。

其中 $k$ 为链表总条数，$n$ 为所有链表节点总数。

实现点评

  • 优点：代码复用「合并两个有序链表」这一最基础、最熟悉的例程，逻辑非常清晰。
  • 缺点：前面合并出的长链表会反复参与后续合并，累计代价是 $O(nk)$。若链表条数很多，性能不理想——这正是分治解法（解法 5、6）要解决的问题：让每条链表只参与 $O(\log k)$ 次合并。

4. 最小堆解法（Heap / Priority Queue）

思路

我们希望每次都能以尽可能高的效率在所有 k 条链表的当前头节点中选出最小值。与其每轮线性扫描 k 个头节点，不如借助最小堆（优先队列）：

  • 把每条非空链表的头节点压入堆（按节点值排序）；
  • 堆顶始终是值最小的节点；
  • 弹出堆顶，接入结果链表，再将该节点的next（若存在）压入堆；
  • 重复直到堆空。

这样每一步都能以 $O(\log k)$ 的时间选出全局最小节点。

算法步骤

  1. 创建最小堆。
  2. 遍历所有链表，将每个非空链表的头节点（按节点值作为键）压入堆。
  3. 创建 dummy 节点，cur指向它。
  4. 当堆非空时：
    • 弹出值最小的节点；
    • 接到cur.next，cur前移；
    • 若该节点有next，把next压入堆。
  5. 堆空时，所有节点已按序合并完毕。
  6. 返回dummy.next。

参考实现（Python，借助包装类实现堆序比较）

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class NodeWrapper: def __init__(self, node): self.node = node def __lt__(self, other): return self.node.val < other.node.val class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: if len(lists) == 0: return None res = ListNode(0) cur = res minHeap = [] for lst in lists: if lst is not None: heapq.heappush(minHeap, NodeWrapper(lst)) while minHeap: node_wrapper = heapq.heappop(minHeap) cur.next = node_wrapper.node cur = cur.next if node_wrapper.node.next: heapq.heappush(minHeap, NodeWrapper(node_wrapper.node.next)) return res.next

各语言最小堆实现要点

不同语言的最小堆写法差异明显，仓库源码 java/0023-merge-k-sorted-lists.java 的Solution1给出了 Java 版本，其核心是PriorityQueue<ListNode>配合 Lambda 比较器(a, b) -> a.val - b.val：

PriorityQueue<ListNode> queue = new PriorityQueue<>((a, b) -> a.val - b.val); for (ListNode node : lists) { if (node != null) queue.offer(node); } ListNode dummy = new ListNode(0); ListNode current = dummy; while (!queue.isEmpty()) { ListNode node = queue.poll(); current.next = node; current = current.next; if (node.next != null) queue.offer(node.next); } return dummy.next;
  • C++：std::priority_queue默认是大顶堆，必须传入比较器auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };将其反转为小顶堆（见 cpp/0023-merge-k-sorted-lists.cpp 中被注释的 baseline 版本）。
  • Go：标准库没有泛型堆，需要自定义NodeHeap类型并实现heap.Interface的Len/Less/Swap/Push/Pop五个方法（见 go/0023-merge-k-sorted-lists.go 中的堆实现）。
  • JavaScript：使用MinPriorityQueue((x) => x.val)按节点值构造最小优先队列。
  • Rust：BinaryHeap默认是大顶堆，需用Reverse(node.val)包裹后压入，从堆中弹出时再解包（见 rust/0023-merge-k-sorted-lists.rs）。

复杂度分析

  • 时间复杂度：$O(n \log k)$。每个节点入堆、出堆各一次，每次堆操作 $O(\log k)$。
  • 空间复杂度：$O(k)$，堆中最多同时存在 k 个节点。

其中 $k$ 为链表总条数，$n$ 为所有链表节点总数。

实现点评

堆解法是时间与空间的良好折中：相比解法 2、3 的 $O(nk)$ 时间，它把单次选最小值从 $O(k)$ 降到 $O(\log k)$；相比暴力解法的 $O(n)$ 空间，它只需要 $O(k)$。这是面试中最推荐的方案之一。

5. 分治（递归版，Divide And Conquer - Recursion）

思路

与一次性合并 k 条或按顺序逐个合并不同，分治策略与归并排序的思想同源：

  • 把lists数组从中间一分为二；
  • 递归地把左半部分合并成一条有序链表；
  • 递归地把右半部分合并成一条有序链表；
  • 最后用「合并两个有序链表」的例程把左右两条结果合并。

由于始终按两两配对的方式合并，总工作量相比顺序合并显著减少：每次合并两条链表的时间与其总长度成线性关系，而合并层级约为 $\log k$ 层。

算法步骤

  1. 边界条件

    • 若lists为空，返回null。
    • 递归函数divide(lists, l, r)：
      • 若l > r，返回null；
      • 若l == r，返回lists[l]（只剩一条链表）。

  2. 分（Divide）

    • 计算mid = (l + r) // 2；
    • 递归求解left = divide(lists, l, mid)与right = divide(lists, mid + 1, r)。

  3. 治（Conquer）

    • 用标准「合并两个有序链表」例程合并left与right：dummy 节点 +curr指针，两链表均非空时接入较小节点并推进指针，最后把任一剩余链表整体接上。
    • 返回合并结果。

  4. 最终答案

    • 调用divide(lists, 0, len(lists) - 1)并返回结果链表。

参考实现（Python）

# 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): if not lists or len(lists) == 0: return None return self.divide(lists, 0, len(lists) - 1) def divide(self, lists, l, r): if l > r: return None if l == r: return lists[l] mid = l + (r - l) // 2 left = self.divide(lists, l, mid) right = self.divide(lists, mid + 1, r) return self.conquer(left, right) def conquer(self, l1, l2): dummy = ListNode(0) curr = dummy while l1 and l2: if l1.val <= l2.val: curr.next = l1 l1 = l1.next else: curr.next = l2 l2 = l2.next curr = curr.next if l1: curr.next = l1 else: curr.next = l2 return dummy.next

复杂度分析

  • 时间复杂度：$O(n \log k)$。共 $\log k$ 层，每层合并的总节点数约为 $n$。
  • 空间复杂度：$O(\log k)$。递归调用栈深度为 $\log k$。

其中 $k$ 为链表总条数，$n$ 为所有链表节点总数。

实现点评

  • 优点：递归结构对称优雅，没有堆的额外内存，空间复杂度仅来自递归栈 $O(\log k)$，是理论上最优的一档。
  • 缺点：递归深度与栈空间在某些语言/极端输入下需要注意；此外 Rust 等所有权语言中递归写法需要处理Box的移动语义（仓库的 rust/0023-merge-k-sorted-lists.rs 就采用递归merge配合take()移动节点）。

6. 分治（迭代版，Divide And Conquer - Iteration）

思路

这是分治思想的迭代实现：不递归，而是反复按两两配对合并：

  • 第一轮：合并链表 0 与 1 得 M0、链表 2 与 3 得 M1、链表 4 与 5 得 M2……；
  • 一轮过后链表数量大约减半；
  • 对新得到的链表数组重复该过程，直到只剩一条链表。

每一对的两两合并仍是标准的「合并两个有序链表」。这与归并排序的 merge 步骤结构一致，工程上无递归栈风险。

算法步骤

  1. 若lists为空，返回null。
  2. 当链表数量大于1时循环：
    • 创建空数组mergedLists；
    • 以步长2遍历lists：
      • l1 = lists[i]；
      • l2 = lists[i + 1]（若存在），否则为None；
      • 用mergeList(l1, l2)合并并追加到mergedLists；
    • 令lists = mergedLists。
  3. 循环结束时，lists[0]即为完整有序链表，返回它。

参考实现（Python）

# 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: List[Optional[ListNode]]) -> Optional[ListNode]: if not lists or len(lists) == 0: return None while len(lists) > 1: mergedLists = [] for i in range(0, len(lists), 2): l1 = lists[i] l2 = lists[i + 1] if (i + 1) < len(lists) else None mergedLists.append(self.mergeList(l1, l2)) lists = mergedLists return lists[0] def mergeList(self, l1, l2): dummy = ListNode() tail = dummy while l1 and l2: if l1.val < l2.val: tail.next = l1 l1 = l1.next else: tail.next = l2 l2 = l2.next tail = tail.next if l1: tail.next = l1 if l2: tail.next = l2 return dummy.next

复杂度分析

  • 时间复杂度：$O(n \log k)$。
  • 空间复杂度：$O(k)$。每轮需要新建中间结果数组mergedLists（存放约一半数量的链表头指针）。

其中 $k$ 为链表总条数，$n$ 为所有链表节点总数。

实现点评

  • 优点：无递归栈，逻辑直白，且每次合并都是纯两两合并，非常契合工程实现。
  • 缺点：每轮都要构造中间数组，空间为 $O(k)$（可接受，因为 $k \le n$）。

值得注意的是，本仓库的主实现正是这一迭代分治方案，但各语言在细节上有不同变体：

  • Python：python/0023-merge-k-sorted-lists.py 完整实现了上述while len(lists) > 1的两两合并循环。
  • C++：cpp/0023-merge-k-sorted-lists.cpp 采用原地交替合并的变体：维护当前有效链表数n，每一轮把lists[i]与lists[n - i - 1]合并后写回lists[i]，再令n = (n + 1) / 2，全程不新建数组，空间复杂度可视为 $O(1)$；文件头注释明确指出该方案用于在最小堆基础上进一步优化空间。
  • Java：java/0023-merge-k-sorted-lists.java 的Solution2使用interval从 1 开始倍增的迭代归并变体：lists[i] = merge(lists[i], lists[i + interval])，步长每轮翻倍，同样 $O(n \log k)$ 时间、$O(1)$ 额外空间。
  • Go：go/0023-merge-k-sorted-lists.go、Rust：rust/0023-merge-k-sorted-lists.rs 均采用步长 2 遍历 + 新建中间数组的迭代分治；Rust 版通过lists[i].take()移动Option<Box<ListNode>>所有权，避免克隆。

仓库多语言实现速查

本仓库为本题提供了 14 种语言的完整实现，除上文提到的之外还包括：

  • C：c/0023-merge-k-sorted-lists.c
  • C#：csharp/0023-merge-k-sorted-lists.cs
  • JavaScript：javascript/0023-merge-k-sorted-lists.js
  • Kotlin：kotlin/0023-merge-k-sorted-lists.kt
  • Ruby：ruby/023-merge-k-sorted-lists.rb
  • Swift：swift/0023-merge-k-sorted-lists.swift
  • TypeScript：typescript/0023-merge-k-sorted-lists.ts

这些实现与本文六种解法一一对应，可作为你学习、对比与本地运行验证的参考素材。所有语言共享同一套ListNode数据结构定义，各语言仅需适配自身语法与标准库（如堆、排序 API）即可。

常见陷阱（Common Pitfalls）

1. 未处理输入数组中的空链表

输入数组lists可能包含null或空链表。若在读取节点值之前不检查非空性，会触发空指针异常（Null Pointer Exception）。处理任何链表前务必先验证其非空。

2. 忘记推进被选中链表的指针

选出 k 条链表中值最小的节点后，必须把该链表的头指针移到下一个节点。若遗漏这一步，同一个节点会被反复选中，导致死循环。

3. 最小堆的比较器方向写反

使用优先队列/最小堆时，比较器必须正确地按节点值比较。部分语言默认堆是大顶堆（如 Python 的heapq按负值技巧、C++ 的priority_queue、Rust 的BinaryHeap），比较方向写反会把最小堆变成最大堆，输出顺序错误。

4. 结果链表不使用 dummy 头节点

不用 dummy 头节点构建结果链表时，需要为第一个节点单独写特殊处理逻辑，代码易错且啰嗦。使用 dummy 节点可以对所有节点统一处理，最后返回dummy.next即可。

5. 迭代过程中错误地修改输入数组

在「逐一两两合并」与「分治」方案中，回写lists数组时要格外小心：一边遍历一边覆盖元素可能导致合并结果错误或链表被跳过。要么使用独立的数组存放合并结果（如迭代分治的mergedLists），要么严格控制下标（如 C++ 版的lists[i]与lists[n - i - 1]交替合并、Java 版的 interval 倍增写法）。

总结

合并 K 个有序链表是一道"一题多解"的经典链表题，六种解法构成一条清晰的渐进优化链：

  1. 暴力收集 + 排序（$O(n \log n)$ / $O(n)$）：最简单，但抛弃了输入已有序的信息；
  2. 每轮线性扫描取最小（$O(nk)$ / $O(1)$）：不占空间，但扫描代价高；
  3. 逐个两两合并（$O(nk)$ / $O(1)$）：复用「合并两个有序链表」，思路自然；
  4. 最小堆（$O(n \log k)$ / $O(k)$）：用优先队列把"找最小"降到对数级，时间空间均衡；
  5. 递归分治（$O(n \log k)$ / $O(\log k)$）：归并排序思想，空间最优；
  6. 迭代分治（$O(n \log k)$ / $O(k)$）：无递归栈，工程上最常用，也是本仓库多语言主实现采用并给出原地变体的方案。

面试中建议优先掌握最小堆与迭代分治两种方案，并理解其复杂度推导；结合本仓库 articles/merge-two-sorted-linked-lists.md 与 hints/merge-k-sorted-linked-lists.md 打牢前置基础，再对照 14 种语言源码逐一验证，即可彻底吃透本题。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/9/18 21:26:58

青龙面板部署京东自动评价返京豆脚本完整教程

青龙面板跑京东相关的自动化脚本&#xff0c;圈内已经不是什么新鲜事了&#xff0c;签到、开卡、领豆的脚本满天飞。但"商品自动评价返京豆"这块&#xff0c;能讲清楚原理、能自己改脚本的人并不多。我去年把一套评价脚本从零写好&#xff0c;放到青龙面板上稳定跑了…

作者头像 李华
网站建设 2026/9/18 21:23:33

机载激光雷达数据处理全流程：从系统组成到DEM生成

简介&#xff1a;这是一份面向测绘、电力、林业及环境监测领域初学者与从业者的机载激光雷达技术入门课件&#xff0c;系统讲解LiDAR基本工作原理、硬件组成、数据预处理与点云生成流程&#xff0c;并涵盖DEM生成、目标提取及典型应用场景&#xff0c;内容由浅入深&#xff0c;…

作者头像 李华
网站建设 2026/9/18 21:20:26

ascend-transformer-boost 中 Unpad 算子的源码路径导航与实现原理

ascend-transformer-boost 中 Unpad 算子的源码路径导航与实现原理 【免费下载链接】ascend-transformer-boost 本项目是CANN提供的是一款高效、可靠的Transformer加速库&#xff0c;基于华为Ascend AI处理器&#xff0c;提供Transformer定制化场景的高性能融合算子。 项目地…

作者头像 李华