LeetCode 88. 合并两个有序数组：从后往前的原地合并

题目与「空间约束」的特殊性

LeetCode 88：nums1 和 nums2 两个有序数组，nums1 的长度是 m+n（后 m+n-m 个位置填 0 占位），把 nums2 合并进 nums1，原地排序。

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6]
输出：nums1 = [1,2,2,3,5,6]（原地修改，无返回值）

「原地」是这道题的灵魂约束：如果允许 O(m+n) 的额外空间——归并排序的合并步骤（新数组双指针从头比较——「从头」的写法人人会写——写完复制回 nums1——这不是题目想要的）。「原地」的难点：nums1 的有效数据在前 m 位、空位在后 n 位——从前往后写会覆盖 nums1 自己的数据（[1,2,3,0,0,0] 从头写 2——覆盖了 3——「数据丢失」）——「约束改变算法方向」——从头不行，那就从尾——「从后往前」的灵感来自「空位在后」**。

从后往前的三指针

三个指针：p1（nums1 有效数据的末尾，m-1）、p2（nums2 的末尾，n-1）、p（写入位置的末尾，m+n-1）——「从最大的开始比」：nums1[p1] 与 nums2[p2] 取大者放到 nums1[p]——「尾部空位」保证写入不覆盖任何有效数据——因为写入位置 p 始终在 p1 和 p2 的「右侧」——「p 永远 ≥ p1」的不变量——从后往前，右边永远比左边先填——「写入的右边性」保证无覆盖。

def merge(nums1, m, nums2, n):
    p1, p2, p = m - 1, n - 1, m + n - 1
    while p2 >= 0:                       # nums2 用完即结束
        if p1 >= 0 and nums1[p1] > nums2[p2]:
            nums1[p] = nums1[p1]
            p1 -= 1
        else:
            nums1[p] = nums2[p2]
            p2 -= 1
        p -= 1

「循环条件是 p2 >= 0」的巧思：循环到 nums2 用完就停——「nums1 剩下的已经在正确位置」——p1 没走完时，剩余的 nums1 前缀本来就在原地——「不需要搬动」——这是「从后往前」的第二个红利——对比「从前往后」：写完后还要处理剩余——**「方向的巧妙」省掉了收尾。

「逐轮追踪」（[1,2,3,0,0,0] + [2,5,6]）：p=5：比 3 与 6 → 写 6，p2=1 → p=4：比 3 与 5 → 写 5，p2=0 → p=3：比 3 与 2 → 写 3，p1=1 → p=2：比 2 与 2 → else 写 2（nums2），p2=-1 → 循环结束——nums1 = [1,2,2,3,5,6] ✓——「else 的细节」：相等时走 else 写 nums2 的——「相等时取哪个」不影响正确性（值相同——但「稳定性」（合并排序的稳定性讨论——「相等取 nums2」破坏稳定——「相等取 nums1」保持稳定（> 改 >=——「稳定性」在合并中的意义（多字段排序时——「稳定性」是好工程习惯。

「从后往前」的思维与归并的本源

「反向思维」的通用性：「从后往前」在数组题中的出现清单：本题（原地合并）、「原地删除重复项」（LeetCode 26/27——双指针保留前缀——「保留型的原地操作」用双指针、「覆盖型」用从后往前——「原地操作的两个流派」：保留型（读写指针同向、写 ≤ 读——「写指针永远不超读指针」——无覆盖；覆盖型（反向写入——「尾部的空位」是前提——「反向的前提是尾部有空余」——本题的空位是题目给的、其他题要自己构造（「旋转数组」——LeetCode 189 的三次反转——「反转三次」的空间 O(1)——「原地操作的技巧库」：双指针、反转、环状替换——「原地」是面试高频约束。

「合并」在归并排序中的本源：本题是「归并排序 merge 步骤」的变体——归并排序的 merge 是「两个独立数组→新数组」（从头、辅助空间）——本题是「一个数组的尾部预留」（从尾、原地）——「merge 的两种实现」：辅助空间版（稳定、简单——「时间 O(m+n) 空间 O(m+n)」）与原地版（「时间 O(m+n) 空间 O(1)」——稳定性破坏——「空间换稳定性」——「归并排序用辅助版、这道题用原地版」——同一个算法两种工程形态——「形态的选择由约束决定」——O(1) 空间约束 → 原地反向——「约束驱动设计」。

「为什么 nums2 的尾部更大」：从后往前的比较（「最大的在尾部」——有序数组的尾部是最大值——「每次写的都是剩余最大」——写入位置的降序填充——「降序填充」的正确性——「p 位置的值 = 剩余元素的最大值」的不变量——「不变量思维」再次出场（二分篇的区间不变量——「不变量」是数组双指针题的通用验证法**。

链表操作的高频问答

收尾前回答三个高频问题。「链表的边界：头节点和空链表怎么处理？」——「dummy 的统一」：哨兵节点的消除——「dummy.next」是真头——「特判的消除」——「哨兵」在合并、删除、反转的统一——「哨兵」是链表代码的「减 bug 神器」。「链表操作的时间复杂度怎么算？」——「链表的复杂度」：访问 O(n)（没有随机访问——「与数组对比」（数组 O(1) 访问、链表 O(n)——「插入删除」O(1)（已知位置——「数组插入」O(n)——「链表的优势」是插入删除——「劣势」是访问——「选型的依据」——「业务特征」决定结构。「什么时候用链表而不是数组？」——「链表的适用场景」：频繁的中间插入删除（「LRU 的链表」——大小不确定（「动态」——「数组的优势」：随机访问、缓存友好（「CPU 缓存」的局部性——「数组的连续内存」——「缓存行」的利用——「链表的不连续」——「指针跳转」的缓存 miss——「实践中数组的缓存优势」常常胜过链表的插入优势——「工程中链表的真实使用率」低于理论——「数组+索引」常常替代链表——「链表的真实场景」：LRU 的双向链表、「高并发插入」、「内存分配器」——「理论与实践的差距」——「工程决策」要看实测。链表的问答收束：链表的三个心智模型——「哨兵是保镖（消除边界）、画图是导航（指针追踪）、实测是裁判（数组可能更快）」——「链表的指针操作」要靠画图——「数组与链表的选型」要看实测——「理论告诉方向、实测给出答案」——这是所有数据结构选择的通法。

原地合并的进阶问答：方向推导、无空位的原地与工程 merge

问题一：如果 nums1 没有预留尾部空位，还有 O(1) 空间的解法吗？——没有直接的——「从后往前」的全部底气来自尾部有现成的写空间。没有空位时的选项：新开数组做标准归并（O(m+n) 辅助空间、稳定、人人会写）；或者「先扩展再反向」——多数语言的可变数组可以先补齐占位、再走本题流程（严格说扩容那一步就不止 O(1) 空间了）。真正值得延伸记忆的是旋转数组（LeetCode 189）的三次反转：它演示了「没有空位也能原地换序」的另一条路——利用「反转不改变多重集合、只改变顺序」的性质，O(1) 空间完成环形位移。原地操作的两大流派就此齐全：有空位用反向写入，无空位用反转技巧——面试里能把两个流派各自的适用前提讲出来，原地操作的版图才算完整。

问题二：从前往后写真的不行吗？有没有从前往后反而对的场景？——取决于有效数据与空位的相对位置。本题数据在前、空位在后，从前往后写会把未处理的数据踩掉；把局面镜像一下——若 nums1 的有效数据在后半段、空位在前半段（例如 [0,0,0,4,5,6] 配 nums2=[1,2,3]），从前往后就自然安全，反向反而别扭。所以通用心法不是「永远从后往前」，而是「写入方向必须与空位方向一致，且写入指针永远追不上未读数据」——满足这两条，方向怎么选都对。把「为什么从后往前」抽象到这一层，遇到任何镜像变体都能现场推导方向，而不是背一个固定方向——背方向的人在镜像题上必翻车，推方向的人从不翻车。

问题三：merge 在工程里以什么形态出现？——三个高频场景。外部排序：内存装不下的大文件先分块排序落盘，再做 k 路归并——k 路时不能沿用本题的双指针两两比较（会退化成 O(nk)），要用小顶堆维护「每一路的当前最小」，整体 O(n log k)。数据库的 merge join：两张按连接键有序的表做归并连接，比嵌套循环快几个数量级——它的前提「表有序」正是索引存在的意义之一。日志与时间序列合并：多台机器各自按时间戳有序的日志，归并成全局序列——本题的三指针就是它的最小模型，工程版再叠加相同时间戳的稳定性处理。再往上，语言内建排序也藏着它：Python 的 sorted 与 Java 的 TimSort 都是「归并 + 插入」的混合体，「相等取先者保稳定」的课堂细节在生产排序器里真实存在——学完这道题回头看 Timsort，会发现课堂与生产的距离比想象中近得多。

小结

合并两个有序数组的完整解析：原地约束的方向翻转（从前写覆盖数据——「空位在后」启发从后往前——「约束改变算法方向」）；三指针（p1/p2/p——「p ≥ p1」的不变量保证无覆盖——循环条件 p2 ≥ 0 的巧思——「nums1 前缀不需要搬动」的红利）；归并的本源（merge 的两种形态——辅助空间稳定 vs 原地 O(1)——「稳定性」的取舍——相等取谁保稳定）；思维泛化（保留型原地用双指针、覆盖型用反向——原地操作技巧库——旋转数组的三次反转）。给学习者的提醒：这道题的难度不在算法（合并人人会写），在「方向的翻转」——「从前往后写会怎样？」——亲自试一次覆盖的错误——错误体验比正确答案更深刻——以及面试时的表达：先说「从头写会覆盖」再给「从后往前」——「展示思考过程」比直接给答案更能体现工程思维。

合并两个有序数组教会的是：当约束看起来「不可能」时，换一个方向——空间在尾部，就从尾部开始写——很多工程难题的答案，不在更复杂的技术里，而在「换个方向再看一眼」。