LeetCode88 合并两个有序数组｜C语言三种解法，逆向双指针最优解（附代码踩坑记录）

前言

LeetCode88是数组与双指针入门必刷经典题，核心难点是原地合并数组，不能新建数组存储结果。很多初学者会写出正向双指针覆盖数据、收尾循环嵌套等bug，本文从暴力、正向双指针、逆向双指针逐层拆解，重点记录我写代码时踩过的坑，适合零基础刷题复盘、面试复习。

一、题目原题

给你两个按非递减顺序排列的整数数组 nums1 和 nums2，以及两个整数 m、n：

• m：nums1有效元素数量；n：nums2有效元素数量
• nums1数组长度固定为 m+n，前m位存有效数据，末尾n位填充0作为空白存储空间
  要求：将nums2合并进nums1，直接修改nums1，最终nums1保持升序，不允许返回新数组。

示例输入：
nums1 = [1,2,3,0,0,0], m=3
nums2 = [2,5,6], n=3
输出：nums1 = [1,2,2,3,5,6]

边界用例：

1. nums2为空：nums1=[1],m=1,n=0 → 数组不变
2. nums1无有效数据：nums1=[0,0],m=0,n=2,nums2=[1,2] → [1,2]

二、解法1：暴力合并后排序（最简写法）

思路

1. 把nums2全部复制到nums1后半段空白位置；
2. 直接对整个nums1数组升序排序。

C语言完整代码

#include <stdio.h>
#include <stdlib.h>

// qsort升序比较函数
int cmp(const void* a, const void* b)
{
    return *(int*)a - *(int*)b;
}

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
    // 将nums2拷贝到nums1尾部空位
    for(int i = 0; i < n; i++)
    {
        nums1[m + i] = nums2[i];
    }
    // 整体排序
    qsort(nums1, m + n, sizeof(int), cmp);
}

复杂度与优缺点

• 时间：$O((m+n)log(m+n))$，排序消耗主要时间
• 空间：$O(1)$，原地操作
  ✅ 优点：代码极少，上手零门槛
  ❌ 缺点：完全没有利用两个数组本身有序的条件，效率差，面试不推荐作为最优解

三、解法2：正向双指针+临时数组

思路分析

如果直接从前往后往nums1写入小数，会覆盖nums1还未参与比较的原始数据，造成数据丢失。
解决方案：开辟临时数组存放合并结果，合并完成后再拷贝回nums1。

1. 双指针分别从头遍历nums1、nums2；
2. 每次取更小值存入临时数组，对应指针后移；
3. 其中一个数组遍历完毕，把另一个数组剩余元素全部追加；
4. 将临时数组覆盖原nums1。

复杂度

• 时间：$O(m+n)$，仅遍历一次两个数组
• 空间：$O(m+n)$，需要额外数组存储结果

缺点

额外占用内存，不符合题目极致原地优化的需求，仅作为过渡思路理解。

四、解法3：逆向双指针（最优解，时空双优）

核心思想

正向填充会覆盖数据，反向填充不会覆盖有效元素：
nums1尾部是空白0，我们从两个数组末尾取最大值，依次填入nums1尾部空位，填充位置永远是空白或已经处理完的数据，不会丢失未对比的数值。

指针定义

指针	含义	初始值
l1	nums1有效数据最后一位下标	m-1
l2	nums2最后一位下标	n-1
l3	nums1填充位置（合并数组末尾）	m+n-1

执行逻辑

1. 循环条件：l1>=0 && l2>=0，两个数组都有未遍历元素
   • 对比nums1[l1]、nums2[l2]，更大的值存入nums1[l3]
   • 取值指针、填充指针同步自减
2. 循环结束分两种情况：
   • l2<0：nums2遍历完成，nums1前部本身有序，无需操作
   • l1<0：nums1遍历完成，单独循环把nums2剩余元素全部填入nums1

无bug正确C语言代码

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int l1 = m - 1;
    int l2 = n - 1;
    int l3 = m + n - 1;

    // 两个数组都有元素，从后往前选大数填充
    while (l1 >= 0 && l2 >= 0)
    {
        if (nums1[l1] > nums2[l2])
        {
            nums1[l3--] = nums1[l1--];
        }
        else
        {
            nums1[l3--] = nums2[l2--];
        }
    }

    // 若nums2还有剩余元素，全部拷贝到nums1前部
    while (l2 >= 0)
    {
        nums1[l3--] = nums2[l2--];
    }
}

五、本人代码踩坑记录（重点易错点）

错误代码片段

// 错误写法！收尾循环嵌套在主循环内部
while(l1>=0 && l2>=0)
{
    if(nums1[l1]>nums2[l2])
    {
        nums1[l3--]=nums1[l1--];
    }
    else
    {
        nums1[l3--]=nums2[l2--];
    }
    // 致命错误：每次比较完直接清空nums2所有元素
    while(l2>=0)
    {
        nums1[l3--]=nums2[l2--];
    }
}

错误原因

每次完成一次数值对比赋值，立刻执行while(l2>=0)把nums2剩余所有元素一次性塞进数组，打乱逐位对比逻辑，最终数组乱序。

修正方案

处理nums2剩余元素的循环必须放到外层while循环外面，等两个数组对比结束后再统一处理。

六、样例手动推演

输入：nums1=[1,2,3,0,0,0], m=3；nums2=[2,5,6],n=3
初始：l1=2, l2=2, l3=5

1. 3 < 6 → nums1[5]=6，l2=1,l3=4
2. 3 < 5 → nums1[4]=5，l2=0,l3=3
3. 3 > 2 → nums1[3]=3，l1=1,l3=2
4. 2 == 2 → nums1[2]=2，l2=-1,l3=1
   外层循环终止，l2=-1，无需执行收尾循环
   最终数组：[1,2,2,3,5,6]

七、三种解法对比表

解法	时间复杂度	空间复杂度	优点	缺点	面试推荐
合并后排序	$O((m+n)log(m+n))$	O(1)	代码最简单	效率低，未利用有序	⭐
正向双指针+临时数组	O(m+n)	O(m+n)	逻辑易懂	占用额外内存	⭐⭐
逆向双指针	O(m+n)	O(1)	时空最优、原地修改	需要理解反向填充逻辑	⭐⭐⭐⭐⭐

八、刷题总结

1. 本题核心考点：双指针思想、有序数组合并、原地数组数据覆盖问题；
2. 面试标准答案固定为逆向双指针，必须能手写代码并解释正向合并为什么会覆盖数据；
3. 高频bug：拷贝nums2剩余元素的循环嵌套在主循环内部；
4. 拓展：逆向双指针思路可迁移到归并排序、多有序数组合并等题型。