企业官网建设流程全解析

合并两个有序列表，这可能是算法题单里最“不起眼”的题目之一：LeetCode 21 是它，LeetCode 88 也是它，归并排序里那个 merge 环节还是它。可我在面试别人和带新人的过程中发现，能一次写对的人真不多——不是不懂思路，而是指针边界、相等元素、空输入这些细节总在翻车。这篇文章就聚焦一件事：把“合并两个有序数组”和“合并两个有序链表”的原理、代码、复杂度、边界坑位一次讲透。刚入门的同学可以拿它当双指针的第一道完整练习，准备面试的可以直接当错题本复盘。

1. 先啃数组：双指针合并的三种写法与时空账本

1.1 最直观的“另开新数组”解法

数组版的核心思路一句话就能说清：两个指针分别指向两个数组的当前元素，谁小就把谁放进结果数组，对应指针往前走一步；等某个数组走完了，直接把另一个数组剩下的部分整体拼到结果后面。这个思路不依赖任何数据结构技巧，纯粹是用“两个下标”代替人工一张一张比较扑克牌的过程。

def merge_sorted_arrays(a: list[int], b: list[int]) -> list[int]: i = j = 0 res = [] while i < len(a) and j < len(b): if a[i] <= b[j]: res.append(a[i]) i += 1 else: res.append(b[j]) j += 1 # 走到这里说明至少有一个数组已经取完 res.extend(a[i:]) res.extend(b[j:]) return res

这段代码看起来简单，但有三个细节值得琢磨。第一个是 while 条件里的两个判断必须同时成立，一旦某个指针越界就退出循环，然后把剩余部分用切片一次性接上。切片在 Python 里是 O(len) 操作，摊到整个算法里仍然是 O(m+n)，如果你写的是 C 或 Java，这就等价于再写一个循环逐个拷贝，逻辑完全一致，只是写法朴素一些。

第二个细节是我故意用<=而不是<。当两个数组出现相等元素时，<=会把 a 中的元素先放进结果，这样合并结果中相等元素的相对顺序和原数组一致。纯粹在两个独立数组之间做合并时，这个选择好像无所谓；但一旦这个合并函数被归并排序调用，稳定性就直接关系到排序结果是否满足“相等元素次序不变”的语义。这个点我在第 4 节还会展开。

第三个细节是“另开新数组”不是所有场景都能用。如果题目要求原地合并，或者系统里不允许频繁分配大块内存，就得换思路。很多新手第一次写这道题只记住了“双指针”，却忽略了合并结果的存放位置其实是方案选型的分水岭。

1.2 原地合并：从尾部倒着填的 LeetCode 88 解法

LeetCode 88 是数组版最经典的变形：nums1 的长度是 m+n，前 m 个位置放着有效数据，后面 n 个位置是预留的空位（通常用 0 占位），nums2 有 n 个有效数据，要求把 nums2 合进 nums1，不允许另开数组。

很多人第一次做这道题会惯性从头部开始合并，结果发现 nums1 的有效元素被覆盖了。原因其实很容易想通：nums1 的有效数据紧挨着排在前面，从头部合并时结果也要从头部开始写，写进去的值会先覆盖还没被读到的元素。反过来，如果从尾部开始写，写入位置在 nums1 的末尾空闲区，永远碰不到还没处理的前段数据。这个“从后往前”的思考方式，是原地数组操作里通用的手法。

def merge_in_place(nums1: list[int], m: int, nums2: list[int], n: int) -> None: p1, p2 = m - 1, n - 1 # 从两个数组的有效尾部出发 tail = m + n - 1 # 合并结果写入位置，从nums1末尾开始 while p1 >= 0 and p2 >= 0: if nums1[p1] > nums2[p2]: nums1[tail] = nums1[p1] p1 -= 1 else: nums1[tail] = nums2[p2] p2 -= 1 tail -= 1 # nums1 还有剩余时不用处理，它们已经在正确位置 while p2 >= 0: nums1[tail] = nums2[p2] p2 -= 1 tail -= 1

这里最反直觉的一点是：为什么最后只需要处理 nums2 的剩余元素，而 nums1 的剩余部分可以完全不管？因为合并结果最终要填满 nums1 的前 m+n 个位置。当 p2 先耗尽时，说明 nums2 的元素已经全部放置完毕，nums1 前段剩下那些元素本来就比所有已放置的元素都小，而且它们已经待在最终位置上，动都不用动；反过来，如果 p1 先耗尽，说明 nums2 还剩若干元素，它们比 nums1 剩余的所有元素都小，必须手动把它们逐个拷贝到 nums1 最前面。理解了这个“谁先耗尽”的对称性，这个函数才算真正吃透。

1.3 多种写法的复杂度差异与选型

把常见写法放一起看，复杂度差异一目了然：

很多人会问：Python 里一行sorted(a + b)就搞定了，为什么还要手写双指针？原因有两层。第一层，面试和笔试考的是你对“有序性”的利用，两个有序数组线性合可以做到 O(m+n)，你用排序就退化成了 O((m+n)log(m+n))，数据量一大就是几个数量级的差距。第二层更接近工程现实：真正的系统里要合并的往往不是“内存里两个数组”，而是两个有序文件、两个数据库游标、两个外部排序产物，它们根本没法整体装进内存再排序，只能靠双指针逐条推进、逐条写出。

选型上我的经验是：能另开新数组就尽量另开，代码最简单，不容易出边界 bug；只有当内存受限或者题目明确要求原地时才用尾部倒填，而且写完后一定要拿一两个小用例在纸上把指针走一遍。比如nums1=[1,2,3,0,0,0], m=3, nums2=[2,5,6], n=3这个标准用例，正好覆盖了“相等元素”和“p2 未耗尽”两个分支，我在面试现场也经常用它验证候选人的代码。

2. 再啃链表：虚拟头节点与原地拼接的诀窍

2.1 先定义节点，再写递归：代码最短但没你想的那么安全

链表和数组最大的不同在于：数组元素在内存里连续排布，可以通过下标直接访问；链表每个节点独立分配，只能靠 next 指针一个接一个找。所以链表的合并问题，本质上不是“把数据搬到新容器”，而是“重新编排节点之间的指向关系”。只要你理解了这个前提，后面无论递归还是迭代，都是在回答同一个问题：当前这一步该把哪个节点挂在结果链表的尾部。

先看递归写法。递归的思路很干净：比较两个头节点的值，谁小谁就作为合并结果的头节点，然后让它的 next 指向“剩余部分合并后的结果”。这个定义是自洽的，因为剩余部分依然是两个有序链表，调用同样的函数即可。

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def merge_two_lists(l1: ListNode | None, l2: ListNode | None) -> ListNode | None: if l1 is None: return l2 if l2 is None: return l1 if l1.val <= l2.val: l1.next = merge_two_lists(l1.next, l2) return l1 else: l2.next = merge_two_lists(l1, l2.next) return l2

这段代码背下来很容易，但我必须提醒两件事。第一，递归深度是 O(m+n)。当链表长度到十万、百万级时，函数调用栈可能直接爆掉，实际工程里很少有人用递归写这种合并，只有面试官明确说“输入规模不大”或者你清楚当前语言对递归深度的限制，才优先选它。第二，递归里每个节点的 next 都被重新赋值，意味着原链表结构已被修改，如果调用方还指着旧链表做后续操作，就会出现不可预期的结果。这两个问题在迭代版本里同样存在，但递归把“修改输入”这件事藏得更深，更容易被忽略。

2.2 迭代解法：虚拟头节点为什么能避免一堆 if

工程上更常见的写法是迭代加虚拟头节点。虚拟头节点（dummy head）是链表操作里一个非常实用的技巧：先创建一个不存业务数据的节点，让 cur 指针从它开始，合并过程中不断把较小节点接到 cur.next，最后返回 dummy.next 就是真正的头节点。这个技巧在很多链表题目里都通用，包括删除倒数第 k 个节点、反转区间、两两交换节点等，学会一次受益终身。

def merge_two_lists_iter(l1: ListNode | None, l2: ListNode | None) -> ListNode | None: dummy = ListNode() cur = dummy 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 if l1 is not None else l2 return dummy.next

虚拟头节点的好处在于把“第一个节点怎么选”这个特殊分支消掉了。如果不用 dummy，你得先比较 l1 和 l2 的头节点，把小的单独定成结果头节点，再进入循环——这就要多写一段 if，而且很容易在“清空了一个链表之后”漏处理另一种情况。用 dummy 之后，所有节点一视同仁，每个分支都只做“接节点、推进指针”两件事，结构对称，逻辑清晰。

尾部那句cur.next = l1 if l1 is not None else l2是整个函数最容易写错的地方。有人会写两个 while 循环把剩余节点逐个接上，虽然没错但完全没必要——链表本身就是一串节点，把当前 cur 的 next 直接指向剩余链表的头节点，剩下的节点会自动跟着走，一次赋值就完事。这也是链表问题和数组问题在习惯上的一个重要差异：数组合并需要逐元素拷贝，链表合并只需要“搭桥”，千万被数组的思维带偏。

2.3 原地拼接的代价：原链表被改掉了

上面两种链表的合并代码都没有创建新节点，只是调整了 next 指针，因此额外空间是 O(1)，这也是链表合并比数组合并“省空间”的根本原因。但这个“省”是有代价的：两个输入链表的内部结构被破坏了，合并结果是原链表节点的重新组合。

如果你的业务需求是“合并后两个原始链表还要继续保留”，那就不能原地拼接，得在合并过程中 new 出新节点，逐个复制 val。相当于用 O(m+n) 的时间外加 O(m+n) 的空间去建一条全新的链表。很多刚接触链表的人容易忽略这个选择点，等发现原链表被改了才反应过来，数据已经回不去了。我的建议是：动手写代码前先问清楚“是否允许修改输入”，这比任何代码优化都重要。面试时这个追问本身也是加分项，说明你有工程意识，而不只是在背题。

3. 数组与链表合并思路的差异，本质是内存模型差异

3.1 随机访问与顺序访问决定了各自的写法

数组支持 O(1) 的随机访问，所以双指针可以直接用下标算术：i、j、tail 都是整数，比较、赋值、自增全在常数时间内完成，整个合并过程只是一串下标游戏。链表只能通过遍历逐个访问，你没法直接用“下标”找到第 k 个节点，但链表有一个数组没有的优势：只要拿到某个节点的指针，改写它的 next 就是 O(1) 时间。

这两种访问模型决定了写法的差异。数组版的代码重心在“管理下标”，你得反复确认 i、j、tail 有没有越界；链表版的代码重心在“管理指针的指向关系”，你得确认每次 cur.next 赋值后，下一个要处理的节点有没有被及时保存。最常见的链表 bug，就是节点被接走后，用于遍历的指针还指着已经被“抛弃”的旧位置，导致后面的访问跳到错误节点甚至空指针。

理解了这个模型差异，你会发现很多所谓的“链表题套路”其实都源自同一个需求：在只能顺序访问的前提下，把指针操作组织得尽量少出岔子。虚拟头节点是为了省去头部分支，先保存 next 再改写指针是为了防止丢失后续节点，这些技巧不是孤立的，而是内存模型逼出来的通用解。

3.2 空间复杂度的账要从“能不能原地写”开始算

数组要原地合并，前提是结果数组有足够的剩余容量。回到 LeetCode 88 的设定，nums1 的长度正好是 m+n，所以能倒填；但如果题目给你两个等长的普通数组，要求返回合并结果，那就必须分配一个新数组，额外的 O(m+n) 空间躲不掉。原因是数组的插入操作本身是 O(n) 的，在中间位置插入一个元素要整体后移，逐个插入的话总复杂度会退化到 O(m*n)，完全不现实。这也是为什么数组版合并永远在讨论“会不会覆盖数据”“有没有预留空间”，而不是“能不能少开一个数组”。

链表则完全没有这个限制。节点与节点之间靠指针连接，我只要把前一个节点的 next 指向另一个节点，就完成了“插入”，不需要移动任何数据。所以在“不允许额外空间”的约束下，链表合并天然比数组合并更友好。这个差异也解释了为什么归并排序用在链表上可以做到 O(1) 额外空间，用在数组上却必须 O(n)：数组归并要暂存结果才能保证不覆盖，链表只要改指针就够了。

3.3 缓存局部性：同样 O(m+n)，实际跑起来差好几倍

复杂度相同不代表性能相同。数组元素连续存放，CPU 缓存友好，顺序遍历时能批量预取相邻数据，实际吞吐非常高；链表节点散落在内存各处，每访问一个节点都可能触发一次缓存未命中，也就是常说的指针追逐（pointer chasing）。当数据量达到百万级时，链表合并比数组合并慢 3 到 10 倍都不夸张，这在 LeetCode 上跑大用例时体感非常明显。

这个差距在面试里可能只是“时间复杂度都是 O(m+n)”一句话带过，但在真实系统里往往决定方案选型。比如要合并两个几千万行的有序日志文件，用链表结构在内存里倒腾永远是下策；正确做法是像外部排序那样，用文件游标配合读缓冲做归并，一次只保留少量数据在内存里，其余的流式写出。理解这层差别，比多记几段模板代码实用得多——面试官问到“如果数据量大到放不进内存怎么办”时，能答出这一层的人很少。

4. 边界条件与高频踩坑清单：让代码一次过审

4.1 空输入与一方提前耗尽

最容易翻车的地方其实不在主循环，而在主循环退出之后。数组版退出循环有两种可能：a 走完了，或者 b 走完了，你必须两种情况都处理。前面代码里两个 extend 就是干这个的；如果有人只 extend 了其中一个，遇到另一种情况就会丢数据，而且这种 bug 在“两数组长度差不多”的用例里根本测不出来，必须专门构造一短一长的输入才能暴露。

链表版同理，while l1 and l2退出后，剩余部分可能是 l1 也可能是 l2，所以要么用条件表达式，要么写两个 if 分别接。空输入的检查也要养成习惯：链表版两个参数都是 None 时，递归写法的前两个 if 会直接兜住，迭代写法里 while 不进入，cur.next = None，返回 dummy.next 也是 None，都天然正确。数组版两个空数组时，res 本身就是空数组。这些情况代码都能自然处理，前提是你别在开头画蛇添足地写什么if not a: return None——因为“空数组”的正确语义应该是“合并另一个数组的结果就是另一个数组本身”，直接返回 None 会把调用方坑了。

4.2 相等元素取哪个：稳定性的微妙差别

前面提到数组版用<=保证稳定性。链表版同样建议用<=，让 l1 里的相等元素先被接走。在单纯的合并题里这个选择似乎无所谓，但如果你把合并函数直接拿去做归并排序的 merge 阶段，用<就会让相等元素的相对次序悄悄反转，而稳定排序的硬性要求恰恰是“相等元素次序不变”。等到上层依赖这个性质做二次排序时，结果就会和预期不符，而且这种 bug 极其隐蔽，单测里不专门构造相等元素根本发现不了。

还有一个和稳定性相关的坑藏在原地倒填的数组版本里。倒填是从大到小放置，所以比较时用>来决定“把 nums1 的放下去”还是“把 nums2 的放下去”。如果你在这里也写成>=，相等元素中 nums2 的会被优先放到末尾，最终稳定性和正向合并就不一致。这不是运行错误，但会导致同一个合并逻辑换个方向结果不同，多路归并时行为会很诡异，测试覆盖很容易漏掉这个分支。

4.3 C/C++ 版本里最容易翻车的三个点

如果面试或工作环境是 C/C++，链表合并会多出几个“语言层”的坑。先看代码，再逐个说坑：

struct Node { int val; struct Node *next; }; struct Node* merge_lists(struct Node *a, struct Node *b) { struct Node dummy = {0, NULL}; struct Node *cur = &dummy; while (a && b) { if (a->val <= b->val) { cur->next = a; a = a->next; } else { cur->next = b; b = b->next; } cur = cur->next; } cur->next = a ? a : b; return dummy.next; }

第一个坑是虚拟头节点本身。它是在栈上声明的局部变量，函数返回后局部变量就销毁了，所以只能返回dummy.next，绝对不能把&dummy返回出去，否则就是典型的悬空指针。第二个坑是“消费”语义：这个函数把传入链表重新编排了，原链表的头节点引用一旦交给返回值，旧链表就名存实亡，如果你之后还想遍历 a，行为完全不可预测。第三个坑是如果题目要求返回全新链表而你需要动态分配节点，就要保证每个 new 出来的节点最终都被挂进结果链表中，既不能漏挂造成内存泄漏，也不能多挂造成循环引用，写完最好用地址列表从头到尾核对一遍。

4.4 一份可以直接对照的边界用例表

我平时写这类题目会固定跑一组用例，覆盖所有分支，这里列出来供你直接照抄：

这些用例跑通后，代码的正确性基本就稳了。数组版我还会多跑一个 LeetCode 88 的用例：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3，它同时覆盖了“p2 未耗尽”和“相等元素”两个分支，是我在所有面试场合都会先手推一遍的标准测试。

5. 从合并两个到合并 K 个：面试进阶与真实工程场景

5.1 合并 K 个有序链表：优先队列登场

“合并两个”学会之后，面试官最常见的追问是“如果给你 K 个有序链表呢”。朴素想法是两两合并：第 1 个和第 2 个合并，结果再和第 3 个合并，直到合并完所有。这样每合并一次要重新遍历一遍当前结果，总复杂度 O(k * N)，N 是节点总数，k 越大浪费越明显——前 k 次合并都在反复扫描同一批已经排好序的节点。

更好的做法是用优先队列（最小堆）维护 K 个链表的当前头节点，每次从堆里弹出最小节点接进结果，再把它在原链表中的 next 节点推入堆。这样每个节点只被处理一次，堆操作是 O(log k)，总复杂度 O(N log k)。

import heapq def merge_k_lists(lists: list[ListNode | None]) -> ListNode | None: dummy = ListNode() cur = dummy heap = [] for idx, node in enumerate(lists): if node: heapq.heappush(heap, (node.val, idx, node)) while heap: val, idx, node = heapq.heappop(heap) cur.next = node cur = cur.next if node.next: heapq.heappush(heap, (node.next.val, idx, node.next)) return dummy.next

注意我在堆里存的是(node.val, idx, node)三元组而不是只存节点。原因很实际：Python 的元组在 val 相等时会继续比较第二个元素，而 ListNode 对象之间不能直接比较大小，如果没有 idx 做区分就会抛 TypeError。这个细节我第一次写的时候踩过一次，后来发现不少教材代码也没提，属于“跑起来才知道有问题”的类型。除了堆方案，还有分治合并的写法：先两两合并，再两两合并上一层，复杂度同样是 O(N log k)，两者在面试里都可以讲，堆方案的代码通常更短。

5.2 数据库归并连接与归并排序：工程里的同款套路

合并有序列表不只是笔试题，它几乎是所有“有序数据集归并”场景的基本动作。数据库的排序归并连接（sort-merge join）就是典型：两张表先按连接键排序，然后各拿一个游标像双指针一样往前走，键相等就输出一行，键小的一方继续推进。理解两个有序数组的合并，就理解了 sort-merge join 的心智模型，只是把数组元素换成了表行，把下标换成了游标。

归并排序更是直接建立在这个操作上的。数组版归并排序的 merge 阶段需要 O(n) 额外空间，正是因为我们没法在两个有序子数组之间原地无痛合并；链表版归并排序则可以做到 O(1) 额外空间，因为链表拼接只改指针。这个差异我在第 3 节讲过原理，到归并排序这里正好形成闭环：为什么教科书总说链表归并排序省空间，根源就在内存模型。

外部排序的归并阶段也是一样。比如要对几百 GB 的日志文件排序，先分割成多个有序的小块文件（run），再把这些有序块不断两两归并成更大的有序文件。文件游标本质上就是数组的下标指针，只是数据源从内存变成了磁盘，读取单位从元素变成了缓冲块。能理解这一点的人，再看分布式系统里的多路归并、MapReduce 的 shuffle 合并，都会觉得非常亲切。

5.3 常见变体：去重合并、逆序合并、区间合并

面试里合并有序列表还有几个高频变体，思路大同小异，提前想清楚可以省很多临场推导时间。

去重合并：合并时如果当前节点值和结果末尾的值相等，就跳过当前节点，不接进结果。数组版和链表版逻辑一致，只需维护一个 prev 记录上次写入的值，判断是否重复即可。要注意“去重”的粒度是“连续相等”还是“全局唯一”，有序输入下两者等价，所以不需要额外哈希表。

逆序合并：要求结果按从大到小排列。数组版可以先用正向合并再整体反转，也可以直接反向比较取大者；链表版更简单，比较时取较大者直接拼接，或者正向合并后反转一次。我一般选“比较时取大者”，少一次反转，也少一个边界。

区间合并（比如合并有序区间数组）：把每个区间看成一个元素，比较的是起点和终点而不是单一数值。基本框架还是双指针，但每轮要判断当前区间能否扩展，而不是简单取小值。这个变体在 LeetCode 上对应“合并区间”题，很多人会把它和合并两个有序数组搞混，其实只要抓住“被比较的对象变了，双指针的骨架没变”这一点，就能举一反三。

最后分享一点我自己的体会。合并两个有序列表这道题，我前前后后见过不下五十个人写，真正一次写对的核心不在于记住某个模板，而在于每次写完都自己追问三个问题：主循环退出后剩余数据有没有被接上？相等元素用<=还是<到底影响了什么？这次合并允不允许修改输入数据？把三点想明白，数组版、链表版、递归版、迭代版、K 路合并版就全通了。如果你正在刷题，建议把今天这两段代码默写三遍，然后把 LeetCode 88 和 21 放在同一天连着做，你会发现它们其实是同一道题换了两件衣服。