LeetCode 88 合并两个有序数组：逆向双指针与原地操作的经典范式

每天刷一道算法题，很多人卡住的第一关不是"题解看不懂"，而是"自己动手写的时候总是差一点"。LeetCode 88 合并两个有序数组就是这么一道典型的题：题目描述只有一句话，任何人看到都能读懂，但如果你真把它当"入门题"随手一写，往往会写成一个空间不合格或者边角出 bug 的版本。这道题适合每天坚持算法练习的人用来检验自己对"数组原地操作、双指针、边界条件"的掌握程度；也适合准备面试的人，因为它背后连着的是一大类归并类问题的核心范式。我自己的经验是，这道题刷明白之后，再看归并排序、合并链表、多路归并这些题目，思路明显顺了很多。

1. 这道题被低估了：看似入门，实则在考"原地操作"

1.1 先把题目的潜台词读清楚

题目给了两个已经排好序的数组 nums1 和 nums2。关键设定是：nums1 的物理长度是 m+n，真正参与合并的有效元素只有前 m 个，后面 n 个位置是留给合并结果的空位，通常用 0 占位；nums2 的长度是 n。要求把 nums2 合并进 nums1，让 nums1 整体有序，并且只能原地修改，不能返回新数组。

这里有个经典的误读：很多人看到 nums1 里有 0 就直接当成"要参与比较的元素"。实际上这些 0 是占位符，你只能通过 m 和 n 两个参数来确定有效边界。如果直接遍历 nums1 整个长度，排序结果里就会混进一堆没意义的 0，提交必挂。所以第一步不是写代码，而是把"有效区域"和"占位区域"在脑子里分清楚。

另一个容易忽略的细节是"原地修改"四个字。很多语言里，如果你在函数内部写 nums1 = 新数组，只是让局部变量指向了新对象，根本没改动调用方的原数组。判题器会检查原来的 nums1 对象里的值，所以这种"曲线救国"的写法同样会挂。

1.2 为什么它值得出现在每日算法练习清单里

我平时做每日算法练习，最看重一道题的"信息密度"。LeetCode 88 看起来简单，但它同时压进了三个高频考点：双指针、原地操作、边界条件。这三个点几乎是所有数组类题目的地基。

特别是"空间复杂度 O(1)"这个要求，它逼着你放弃"申请一个新数组再拷贝回来"的舒适区。现实业务里我们确实经常用新数组解决问题，因为可读性最好；但一旦数据量上来、内存紧张，或者面试官想看你有没有优化意识，原地操作的能力就成了分水岭。每天花二十分钟把这种"看起来简单但暗藏玄机"的题吃透，比连续看十篇题解有用得多。

2. 三种常见思路挨个试一遍，看清谁可行

2.1 方案A：拼接后排序——最直观但有两个隐患

人遇到排序后的合并问题，第一反应通常是把所有元素塞进一个新数组，然后调用现成的排序函数。伪代码就这么几行：

javascript复制function merge(nums1, m, nums2, n) {
    const temp = nums1.slice(0, m).concat(nums2);
    temp.sort((a, b) => a - b);
    for (let i = 0; i < temp.length; i++) {
        nums1[i] = temp[i];
    }
}

这段代码确实能通过部分测试，但有两个隐患：第一，排序的时间复杂度是 O((m+n)log(m+n))，而两个数组已经有序，白白浪费了"有序"这个条件；第二，中间用了一个临时数组，空间复杂度是 O(m+n)，不符合题目想考察的原地合并。假如面试官追问一句"能不能不申请额外空间"，这个方案瞬间就失去了竞争力。

不过这条路也不能说白走。它至少帮我们把问题从"如何得到正确结果"推进到了"如何在约束下得到最优结果"。

2.2 方案B：临时数组正向归并——时间对了，空间不够

既然两个数组都有序，最自然的做法是双指针从前往后归并：谁小就先把谁放入结果数组。这是归并排序里 merge 步骤的标准写法：

javascript复制function merge(nums1, m, nums2, n) {
    const result = [];
    let i = 0, j = 0;
    while (i < m && j < n) {
        if (nums1[i] < nums2[j]) {
            result.push(nums1[i]);
            i++;
        } else {
            result.push(nums2[j]);
            j++;
        }
    }
    while (i < m) {
        result.push(nums1[i]);
        i++;
    }
    while (j < n) {
        result.push(nums2[j]);
        j++;
    }
    for (let k = 0; k < result.length; k++) {
        nums1[k] = result[k];
    }
}

时间上是 O(m+n)，已经接近最优了。但空间仍旧是 O(m+n)，问题没完全解决。它的价值在于：把归并的比较逻辑完整跑通了。现在唯一的难处是，怎么把这个逻辑塞进 nums1 自己身上，并且不额外开数组。

2.3 方案C：原地正向插入——元素搬移是噩梦

如果不想要额外数组，直接在 nums1 上从前往后合并行不行？理论上可以，但代价极大。举个例子：nums1 = [1, 3, 5, 0, 0]，nums2 = [2, 4]。正向比较会发现 2 应该插在 3 前面，于是需要把 3 和 5 整体右移一格，把位置腾出来给 2；接着 4 又要插在 5 前面，又得搬移 5 一次。每插入一个 nums2 的元素，最坏都要搬移 O(m) 个 nums1 元素，整体最坏复杂度是 O(m*n)。

正向插入之所以这么痛苦，根源在于"空位在尾部，而新元素希望往前挤"。顺着这个观察再想一步：如果反过来，从尾部开始填元素呢？nums1 的空位本来就在尾部，从尾部填入等于是"把大元素往后放"，完全不需要搬移任何内容。到这里，真正的解题方向就逼出来了。

3. 核心解法：从尾部开始的逆向双指针

3.1 思路的触发点：尾部的空位就是天然缓冲区

题目把 nums1 的长度设计成 m+n，并且明确告诉你后 n 位是空的，这其实是一个非常刻意的提示：尾部留出的空间，就是给 nums2 的缓冲区。既然空位在后，而从后往前填写天然不会覆盖任何有效内容，那为什么不把比较方向反过来，从大往小归并呢？

每次比较 nums1 当前未处理的最大元素和 nums2 当前未处理的最大元素，把更大的那个放到合并后数组的最后一个空闲位置。放完之后，这个位置就"锁死"了，无论后面发生什么都不会再改动它。如此反复，从尾部倒着填回头部，最后得到的数组从左到右看仍然是从小到大。理解这一点，逆向归并的核心就算拿下了。

3.2 三个指针的分工与手动推演

具体实现需要三根指针，各司其职：

• p1 指向 nums1 有效区域的最后一个元素，初始为 m - 1；
• p2 指向 nums2 的最后一个元素，初始为 n - 1；
• p 指向 nums1 物理数组的最后一个位置，也就是合并结果最终要填的位置，初始为 m + n - 1。

每一步都做同一件事：比较 nums1[p1] 和 nums2[p2]，谁更大就把它拷贝到 nums1[p]，然后把对应指针和 p 一起左移。拿一组真实数据手动推一遍：nums1 = [1, 2, 3, 0, 0, 0]，m = 3；nums2 = [2, 5, 6]，n = 3。

初始时 p1 = 2，p2 = 2，p = 5。nums1[2] 是 3，nums2[2] 是 6，6 更大，于是 nums1[5] = 6，p2 变成 1，p 变成 4。第二步比较 3 和 5，5 更大，nums1[4] = 5，p2 变成 0，p 变成 3。第三步比较 3 和 2，3 更大，nums1[3] = 3，p1 变成 1，p 变成 2。第四步比较 2 和 2，因为条件是"nums1 的元素严格大于 nums2 的元素"，2 不大于 2，所以走 else 分支，把 nums2[0] 的 2 放到 nums1[2]，p2 变成 -1，p 变成 1。此时循环结束，结果数组是 [1, 2, 2, 3, 5, 6]，完全正确。

3.3 为什么永远不用担心覆盖未处理的元素

这是逆向归并最精妙的地方。三个指针之间存在一个稳定的不变量：每一步开始前，p = p1 + p2 + 1。因为 p2 始终大于等于 0，所以 p 至少比 p1 大 1，也就是说，p 永远指向 p1 右侧的位置，绝对写不到 nums1 还没处理过的元素上。

我们总是先读取 nums1[p1] 的值，再把它写到更靠后的 nums1[p] 位置，读和写之间始终隔着一个安全距离。这就保证了原地操作的正确性，也是这道题敢把"不借助额外数组"设为硬性要求的原因。写代码之前先想清楚这个不变量，边界条件就会好处理很多。

4. 手写实现：代码、循环条件的取舍与常见坑

4.1 一段可以直接跑的 JavaScript 实现

我用 JavaScript 刷题时最常用下面这版，短且不容易写错：

javascript复制var merge = function(nums1, m, nums2, n) {
    let p1 = m - 1;
    let p2 = n - 1;
    let p = m + n - 1;

    while (p2 >= 0) {
        if (p1 >= 0 && nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1--;
        } else {
            nums1[p] = nums2[p2];
            p2--;
        }
        p--;
    }
};

Python 的写法几乎可以逐行翻译过来：

python复制from typing import List

def merge(nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    p1, p2, p = m - 1, n - 1, m + n - 1
    while p2 >= 0:
        if p1 >= 0 and nums1[p1] > nums2[p2]:
            nums1[p] = nums1[p1]
            p1 -= 1
        else:
            nums1[p] = nums2[p2]
            p2 -= 1
        p -= 1

注意 Python 这个函数不返回任何值，直接就地修改 nums1 列表，这点和题目要求一致。

4.2 循环条件为什么是 while (p2 >= 0) 而不是 while (p1 >= 0)

很多初学者会写成 while (p1 >= 0 && p2 >= 0)，然后发现 nums2 还有剩余元素没放进去，于是又补一段处理 nums2 的循环。这样写当然也能过，但可以更省。

我推荐 while (p2 >= 0) 的理由是：当 p2 < 0 时，说明 nums2 的所有元素都已经放到正确位置了，此时 nums1 剩余的前半部分元素本来就留在原地，不需要再做任何操作。反过来，如果 p1 先变成负数，那正是"nums1 的有效元素已全部用完，剩下全是 nums2 元素"的场景，这时候循环体里的 p1 >= 0 判断会自然地落到 else 分支，把 nums2 剩下的元素依次搬进去。

换句话说，一个循环条件加上一个 p1 >= 0 的前置判断，就同时覆盖了"nums2 先耗完"和"nums1 先耗完"两条分支，根本不需要第三个循环。这个写法信息密度更高，也不容易在分支交接处出错。

4.3 我实际踩过的 4 个隐藏坑

第一，p1 初始化写成 m 而不是 m - 1。看起来只差一个位置，结果是头一个元素永远不会参与比较，最终答案总是差一个数。第二，if 条件里漏写 p1 >= 0。在 JavaScript 里 nums1[-1] 是 undefined，undefined 与数字比较结果是 false，碰巧还能跑对；但同样的代码放到 Java 或 C++ 里就是数组越界异常，所以这个前置判断不是可有可无，是必须的。第三，每一步操作完忘记 p--。一旦少减一次，下一次写入就落在同一个位置，要么死循环要么结果被覆盖。第四，把大于号写成大于等于。等于时优先取 nums1 的元素，多数情况下结果依然正确，但这样会让 p1 更快耗尽，如果不配套处理好 p1 为负的情况，就会在边界处出错。

5. 测试用例设计：把解法逼到死角

5.1 覆盖所有分支的测试样例表

写代码前先列测试用例，是我刷题时坚持了很久的习惯。针对这道题，我每次提交前都会至少跑下面这一组：

这七组用例几乎把代码的全部分支都踩了一遍：p1 提前耗尽、p2 为空、相等元素、最小规模。只要这些测试全部通过，提交一般不会翻车。

5.2 两个特别容易翻车的场景

第一个是 m = 0 而 n > 0。此时 p1 = -1，代码里绝对不能访问 nums1[p1]。我的做法是在 if 前置判断 p1 >= 0，这样 p1 为负时无条件走 else 分支，把 nums2 的元素一个接一个搬到 nums1 里，最后结果正好就是 nums2 原样。

第二个是数组中存在负数。题目只要求有序，没有说一定是非负数。如果 nums2 的元素全是负数，它们最终要放在最前面，逆向归并的逻辑完全不受影响，因为比较的是数值大小而不是符号。但如果你自作聪明用"值等于 0 就是占位符"来判断空位，碰到负数就会把真正的元素误判成空位，结果必然错乱。正确的做法永远是通过 m 和 n 控制边界，不要用具体数值判断占位。

6. 复杂度分析与举一反三的迁移路径

6.1 为什么 O(m+n) 时间 + O(1) 空间就是最优解

这个解法里，每个元素最多被读取一次、被写入一次，处理的步数和 m+n 成正比，所以时间复杂度和归并排序的合并步骤一样。空间上则只有三个指针变量，不随数组规模增长，是严格的 O(1)。合并两个有序数组这类问题最少也要把所有元素看一遍，时间下界就是 O(m+n)；题目又规定不返回新数组，空间下界自然也是 O(1)。换句话说，这已经是这个场景下的最优解。

回头对照前三种方案：拼接排序是 O((m+n)log(m+n)) 时间加 O(m+n) 空间，临时数组归并是 O(m+n) 时间加 O(m+n) 空间，原地正向插入最差 O(m*n) 时间加 O(1) 空间。唯独逆向双指针同时拿到了最优的时间和最优的空间，所以它才会成为那个"标准答案"。

6.2 从合并两个数组到归并排序与多路归并

这道题的解决思路不是孤立技巧，它就是归并排序里 merge 步骤的一个变体。归并排序的分治过程到最后，做的就是"把两个有序子数组合并成一个有序数组"这件事。你在这里练熟的比较逻辑、指针推进方式，几乎可以原封不动地搬到归并排序的实现里。

更进一步，二路归并可以扩展成 K 路归并：维护一个大小为 K 的最小堆，每次从堆顶取出当前最小的元素，再从未完成的数组中补一个进去，整体复杂度是 O(n log K)。很多大数据场景下的外部排序、多路归并，底层都是同一套思想。先吃透最简单的两个数组合并，后面这些复杂变体理解起来就顺了。

6.3 后续可以连刷的同类题目清单

练完这一道，我建议按下面的顺序继续巩固归并类套路：

• 合并两个有序链表：把数组换成链表结构，双指针思路几乎一致，重点在链表的拼接与 dummy 头节点。
• 合并 K 个升序链表：引入优先队列，是面试里的高频题。
• 寻找两个正序数组的中位数：把合并与二分结合起来，复杂度要求苛刻，适合进阶。
• 有序数组的平方：双指针从两端向中间收缩，指针移动方向和此题很接近。
• 数组中的逆序对：在归并排序过程中顺便统计，能加深对 merge 过程的理解。

我的个人建议是别停留在"看懂题解"这一步。隔一天后合上答案，自己从头写一遍；再隔三天，换一种语言再写一遍。等到你能在一分钟内写出 while (p2 >= 0) 这个骨架，并且能清楚解释为什么条件不是 while (p1 >= 0) 的时候，这道题才算真正吃透。那时候你再去做后面的链表合并、多路归并，会发现当初在这道题上花的时间非常值。