合并有序数组与链表：双指针归并、边界处理与工程实践

合并两个有序数组、合并两个有序链表，刷过算法题的人多半都不陌生。但这题看着越简单，越容易在细节上翻车：不是忘了处理剩余元素，就是原地合并时把还没比较的数据覆盖掉，链表版还可能因为没加哑节点把头节点搞丢。而且这两个版本正好覆盖了两种完全不同的存储模型，也对应了工程里最常见的两类合并场景，吃透它们，比背十道题的性价比高得多。这篇就把合并有序数组和链表这组经典操作从头到尾拆一遍，把思路、写法、边界测试和工程选型讲清楚，适合准备面试的人、正在上数据结构课的学生，以及工作中需要写归并逻辑的开发者参考。

1. 合并有序数组和链表前，先想清楚这三点

1.1 隐藏在题目里的三种能力

这类题目之所以在笔试题、面试题里反复出现，是因为它本质上在同时考察三件事：第一，你懂不懂“有序”这个先验条件能带来的效率优势；第二，你对数组和链表这两种数据结构的操作差异是否敏感；第三，你的边界意识是不是到位。

先说“有序”的意义。两个序列如果已经是排好序的，那么每次只需要比较两个序列当前的最小元素，谁小谁就是合并结果中的下一个元素。这个思路叫归并，归并排序里最关键的一步就是从它来的。反过来，如果两个序列无序，你得先排序或者做全量查找，复杂度完全不同。所以看到“有序”两个字，就该条件反射地想到双指针/多指针，而不是去嵌套循环。

再说数据结构本身。数组在内存里是连续空间，可以随机访问任意下标，代价是插入删除需要搬动元素；链表靠指针把节点串起来，插入删除只改指针，但无法直接按下标访问。这个差异决定了数组和链表在合并时的写法完全不像，一个是“填格子”，一个是“接线头”，细节各有各的坑。

第三点，边界意识。两个输入都为空、其中一个为空、两个长度差很大、元素全部相等，这些情况在测试和真实数据里都很常见。能把代码写成“任何输入都不会崩溃、不会丢数据”，才是真正吃透了这道题。

1.2 数组和链表，合并思路为什么不一样

两者的核心思路都是双指针归并：各自维护一个指针指向当前未合并的最小元素，比较后取走一个，指针前进，循环直到某一边耗尽，最后把剩余部分整体接上。但落到具体实现，差别就来了。

数组是连续存储，想要原地合并，通常要利用数组尾部空出来的位置从后往前写，否则很容易覆盖还没处理的元素；如果允许开新数组，那就简单很多，三个指针顺着走即可。链表则没有“元素搬移”这个概念，合并就是不断调整next指针，把两个链表节点依次串成一个新链表，所以核心是节点串联的准确性和剩余链表的直接拼接。

这个差异也提醒我们：写代码之前先问清楚自己面对的是数组还是链表，再决定用哪种写法。很多人的错误不是因为逻辑不懂，而是把数组的思维套到链表上，或者反过来。我自己的习惯是先在纸上画三个格子或三个节点，模拟走一遍，再动手写，基本能避开八成低级失误。

2. 有序数组的归并写法：从后往前的双指针为什么是标准答案

2.1 为什么数组要“从后往前”而不是“从前往后”

LeetCode第88题是最经典的数组版合并场景：nums1长度为m+n，前m个元素是有效数据，后面n个位置默认是0，要求把nums2合并进nums1，结果仍然有序，而且必须原地完成，不返回新数组。

很多人第一次做时下意识从前往后遍历：比较nums1[i]和nums2[j]，把小的塞进nums1的头部。这个思路一落地就会发现问题：小的元素放到头部后，原本存放在那里的元素就被覆盖了，你还需要额外空间保存它，或者把后面所有元素往后挪，一次合并变成O(m*n)的复杂度，得不偿失。

解决办法是把方向反过来。nums1的后半段是空着的，从后往前倒着填，每次把两个数组中当前较大的元素放到nums1的最后，就不会覆盖任何还没处理的元素。这个技巧可以理解成收拾抽屉：正面整理需要把东西搬来搬去，倒着从空位下手，反而一步到位。只要一开始nums1尾部的空位足够放nums2的全部元素，从后往前就是原地合并最稳妥的方案。

2.2 LeetCode 88 完整实现与关键代码注释

直接看实现。我用Python写，逻辑和绝大多数语言一致：

python复制def merge(nums1, m, nums2, n):
    # 三个指针分别指向 nums1 有效区间末尾、nums2 末尾、nums1 总空间末尾
    p1 = m - 1
    p2 = n - 1
    p = m + n - 1

    # 从后往前同步比较，把较大的元素放到 nums1 尾部
    while p1 >= 0 and p2 >= 0:
        if nums1[p1] >= nums2[p2]:
            nums1[p] = nums1[p1]
            p1 -= 1
        else:
            nums1[p] = nums2[p2]
            p2 -= 1
        p -= 1

    # 如果 nums2 还有剩余，直接覆盖到 nums1 前面
    # 不需要处理 nums1 剩余，因为 nums1 自己的元素本来就在原地
    if p2 >= 0:
        nums1[:p2 + 1] = nums2[:p2 + 1]

这段代码有几个地方值得展开说。第一，循环退出条件是 p1 < 0 或 p2 < 0，一旦某个数组的元素全部用完了，另一个数组的剩余部分一定都比已经填进去的元素小（或者相等），直接整体搬到前面即可。第二，我在比较时用的是 nums1[p1] >= nums2[p2]，等于号是有讲究的：当两个元素相等时，优先取nums1的元素，这样结果仍然有序且偏稳定，也避免相等元素来回交替带来的不确定性。第三，nums1[:p2+1] = nums2[:p2+1] 这一步只有在nums2还有剩余的时候才执行；nums1如果还有剩余，不需要任何操作，因为它本来就待在正确的位置上。

如果你不想用切片，也可以用循环逐个写入：

python复制while p2 >= 0:
    nums1[p] = nums2[p2]
    p -= 1
    p2 -= 1

效果完全一样。切片在Python里可读性更好，但如果面试官要求你“不要用语言特性”，用循环写也完全没毛病。

顺嘴提一句，如果题目允许额外空间，也有一个简单版本：新开一个长度为m+n的数组，三个指针从0开始顺着走，谁小放谁，最后把新数组拷回去。这个版本方便理解归并思想，但空间是O(m+n)，面试时最好先说明题意是否允许，再决定用哪种写法。

2.3 复杂度分析与常见变体

从后往前的双指针版，每个元素最多被比较一次、移动一次，时间复杂度稳定在O(m+n)，空间复杂度是O(1)，因为全程只用了三个整型指针，没有数组合并时的额外数组。这也是它能成为“标准答案”的根本原因：在时间最优的前提下，把空间也压到了极致。

实际面试和练习中还经常出现几个变体。第一个是“严格递增”和“非递减”的区别：LeetCode默认“非递减”，也就是允许相等元素，这种情况下合并结果的稳定性需要自己定义；如果题目要求稳定，相等时优先取第一个数组的元素即可。第二个是“两个数组长度差很大”，比如m=10000, n=1，从后往前的写法依然高效，因为循环次数只取决于较短的那个数组的遍历次数加上剩余元素的搬运次数。第三个是延伸成“合并多个有序数组”，那就不再是简单的双指针，而是多路归并，常见的做法是用一个大小为K的最小堆，每次取出当前K个指针指向元素的最小值，再推入该数组的下一个元素，复杂度优化到O(N*logK)。

下面是数组版几个关键参数和要点，整理成表方便对照：

3. 有序链表合并：迭代法、递归法和K路扩展

3.1 迭代法：哑节点真的能省掉一半心智负担

链表版的经典题目是LeetCode 21“合并两个有序链表”。链表节点大概长这样：

python复制class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

迭代法的代码非常短，但有一个关键技巧很多人一开始不知道：加一个哑节点。

python复制def merge_two_lists(l1, l2):
    dummy = ListNode(-1)   # 哑节点，不存实际数据
    cur = dummy            # cur 指向新链表的当前尾节点

    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 else l2
    return dummy.next

为什么需要哑节点？因为新链表的头节点一开始是空的，每合并一个节点才确定下一个节点是谁。如果没有哑节点，返回的时候你得单独记录“第一次到底接了l1还是l2”，代码会多出一堆特判。哑节点的作用就是先提供一个稳定的起点，最终返回dummy.next即可，头节点是空的情况也天然被处理了。

这个技巧在我自己写链表题时的经验是：只要最后需要返回一个从零开始的链表，先放一个哑节点，准没错。不只是合并，链表反转、删除节点也经常借助它来简化逻辑。

迭代过程本身不复杂：每次比较l1和l2当前节点的值，谁小就把cur.next指向谁，然后把那个链表的指针前移。cur也跟着前移，相当于在新链表尾部续上一节。循环退出时必然有一方链表已经走完，剩下的链表每个节点都比已合并部分要大（因为两边都有序），直接把cur.next接过去即可。

复杂度上，时间O(m+n)是必须的，空间O(1)是链表的优势：全程没有新建节点，只是重新排列了现有节点的next指针。这道题最忌讳的做法是把节点值复制出来重新构造链表，那就把链表操作变成了数组操作，既浪费空间又丢失了指针操作的意义。

3.2 递归法：代码最短，但别忽略调用栈

递归版的核心思路是：合并两个链表，可以先看头节点谁小，小的那个作为新链表头部，然后继续合并“去掉头节点后的链表”和“另一个链表”。用代码表达就是：

python复制def merge_two_lists(l1, l2):
    if not l1:
        return l2
    if not l2:
        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

这个写法非常优雅，逻辑上几乎就是题意的直译。递归每次选出当前较小的节点作为结果链表的头，然后让它的next指向“剩余部分继续合并”的返回值。终止条件是某条链表为空，此时直接返回另一条链表，省去了迭代里“拼接剩余”的代码。

但递归有两个代价需要心里有数。第一，空间复杂度成了O(m+n)，因为每次递归都要消耗一层调用栈，最坏情况下递归深度是两个链表长度之和。第二，如果链表特别长，比如生产环境里几百万个节点，递归可能导致栈溢出。所以刷题写递归没问题，工作中处理大数据量时我一般还是倾向迭代法。

补充一个使用上的小细节：递归里if l1.val <= l2.val用的是小于等于，和数组版一样，相等时优先保留第一个链表的节点，行为稳定可预测，打印调试时也不会看到两个相等节点来回跳。

3.3 从两个链表到K个链表：合并的工程化延伸

吃透两个链表后，自然会遇到升级版：合并K个有序链表。这道题在实际工程里出现频率很高，比如多路日志合并、多个有序分片数据合并、数据库有序结果归并等场景，本质上都是“多路归并”。

一种直观做法是把“两两合并”反复执行：先合并链表1和2，再把结果和链表3合并，直到全部合并完。时间必然包含诸多重复比较，最坏会到O(K*N)，K是链表数量，N是总节点数，K大时明显变慢。

更优的做法是借助优先队列（最小堆）。初始化时把所有K个链表的头节点放进堆里，每次从堆里弹出值最小的节点，接在新链表后面，然后把该节点的next重新入堆。这样每次取最小值的复杂度是O(logK)，整体是O(N*logK)。如果追求极致，基于堆的做法就是最佳选择。

python复制import heapq

def merge_k_lists(lists):
    dummy = ListNode(-1)
    cur = dummy
    heap = []

    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))

    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

代码里堆的元组特意带了一个索引i，因为ListNode类型本身不能比较，只有数值会相等，加入索引可以避免堆在值相等时尝试比较ListNode对象而报错。这个坑我实际写的时候踩过，希望你不要再踩。

除了堆，还有分治解法：把K个链表两两配对，每对合并后得到新一轮链表集合，继续配对，直到只剩一个。分治不引入额外堆结构，空间更省，但代码比堆版本稍长。工程上如果对性能敏感，通常优先考虑分治或堆两种方案里“和你现有数据结构最匹配”的那个。

4. 边界测试、易错点与工程选型：把合并代码写稳

4.1 一组值得反复跑的测试用例

很多代码看起来没问题，一跑就崩，多半是边界没测到。我每次写完合并逻辑，都会习惯性跑一组固定用例，这里分享出来：

这些用例别只在脑子里过，建议直接写成测试函数跑一遍。数组版尤其要关注m=0的情况，此时nums1的有效区间为空，你要确保不会去读nums1里那些“预留但无意义”的0值。链表的“一个空”用例则考验你是否在循环前就正确判空了。

4.2 高频翻车点实录

数组版最常见的翻车是忘记“从后往前走”。一旦顺序反了，测试数据一大必崩：小的元素被填到前面，覆盖了还没处理的中间元素，输出直接乱套。解决办法是写之前先在纸上标三个指针，确认每一步移动的方向和覆盖位置。

链表版最常见的问题有三个。第一是忘记保存next再改指针。合并链表时，你可以用l1 = l1.next，因为新链表还没用到l1后续节点；但如果你在更复杂的链表操作里先改了cur.next = l1，又立刻需要访问l1.next，这个next有时已经被覆盖了。非模板操作里，先存next_temp = node.next再改指针是通用安全姿势。第二是接剩余部分时用循环逐个拼接，其实直接cur.next = l1 if l1 else l2就够，循环纯属浪费。第三是递归版本在超长输入上栈溢出，遇到生产级数据量一定改迭代。

还有一个隐蔽的问题：链表合并和反转操作混在一起时，指针指向特别容易错乱。我的经验是，每次修改next之前，先问自己“这个节点的旧next还有没有人用？”如果没人用，直接改；如果有人用，先存变量。

4.3 工程场景里怎么选：是复制还是原地，是循环还是递归

真实项目里并不会每次都说“我要写LeetCode 88”，但同款逻辑很常见：两个有序的配置文件要合并、多个分片结果要归并、日志流要按时间序合并导出。这时候就需要根据条件做选择。

如果数据在数组中，问题允许原地合并且目标数组尾部有空间，优先用从后往前的双指针，省一次数组复制是实打实的性能收益；如果数据不允许原地，比如两个数组都是只读的，那只能新建空间，这时候用普通的从前往后归并即可，不用硬套原地技巧。

如果数据在链表中，优先迭代法，空间O(1)，不会因数据量大而崩溃；如果链表长度很小、代码追求可读性，递归法也完全没问题。我在线上代码里几乎不用递归做链表合并，主要就是怕栈深度不确定，宁可用多几行代码换稳定性。

K路合并的选择也一样：K很小（比如3、4个来源）时，直接两两合并或者纯循环都能接受；K很大，比如几十个文件轮询，用最小堆是唯一合理方案；如果内存紧张，分治法两两合并进程式推进也不错。而且这类归并思想和外部排序的底层实现是相通的，理解了它，以后看大数据框架里的shuffle、merge阶段，体会会很不一样。

最后聊点我自己的习惯。我现在遇到任何和“有序数据合并”相关的需求，第一反应不是直接开写，而是先画出双指针模型，再根据数据结构确认是“填值”还是“接线”。数组版和链表版看着是两道题，底层思维完全一致，只是存储方式改变了操作方式。刷题阶段把它们各写一遍，再把合并K路的版本推一遍，比盲目刷几十道冷门题实在得多。这个三十公分的台阶，值得踩踏实。