LeetCode 56合并区间C代码报heap-buffer-overflow错误求排查修复

• 核心错误：对二级指针int** intervals的内存结构理解错误
  你误以为所有区间的数值存储在连续的内存块中，直接通过*intervals + 偏移的方式访问不同区间的数值，但实际上intervals是指针数组，每个元素intervals[i]是独立申请的堆内存，地址并不连续，访问*intervals + 2已经越界了第一个区间的内存范围，这就是堆缓冲区溢出的根因。你本地测试时大概率是手动构造了连续内存的测试用例，所以没有触发问题，线上环境每个区间独立分配内存，直接触发越界。
• 次要错误：intervalsSize == 1分支直接返回输入的intervals
  该分支你自行申请了returnColumnSizes内存，但返回的是输入参数的内存，线上判题系统通常会分别释放输入内存和输出内存，容易导致double free问题。
• 快排逻辑适配错误
  你实现的快排是针对连续成对int数组的排序，无法直接作用于独立分配的指针数组结构。

1. 重写排序逻辑，适配二级指针结构
   修改快排的partition和quickSort函数，直接操作intervals指针数组，按每个区间的左端点排序，交换的是指针而非int值：

#define BASESIZE 20
#define INCREASE 50

int partition(int** intervals, int low, int high)
{
    int pivot = intervals[low][0];
    int* pivotPtr = intervals[low];
    while(low < high) {
        while(low < high && intervals[high][0] >= pivot) high--;
        intervals[low] = intervals[high];
        while(low < high && intervals[low][0] <= pivot) low++;
        intervals[high] = intervals[low];
    }
    intervals[low] = pivotPtr;
    return low;
}

void quickSort(int** intervals, int low, int high)
{
    if(low < high) {
        int loc = partition(intervals, low, high);
        quickSort(intervals, low, loc-1);
        quickSort(intervals, loc+1, high);
    }
}

2. 重构merge函数主逻辑
   调用快排时直接传入intervals而非*intervals，遍历区间时通过下标访问intervals[i]，不要用指针偏移，同时移除错误的单区间特殊分支，通用逻辑已经覆盖该场景：

int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes){
    int **ret=NULL;
    *returnSize=0;

    quickSort(intervals, 0, intervalsSize-1);

    int size=BASESIZE;
    ret=malloc(sizeof(int*)*size);
    if(!ret) exit(-1);
    *returnColumnSizes=malloc(sizeof(int)*size);
    if(!(*returnColumnSizes)) exit(-1);

    // 初始化第一个区间
    int *tmp=malloc(sizeof(int)*2);
    if(!tmp) exit(-1);
    tmp[0] = intervals[0][0];
    tmp[1] = intervals[0][1];
    ret[0] = tmp;
    (*returnColumnSizes)[0] = 2;
    *returnSize = 1;

    // 遍历后续区间合并
    for(int i=1; i<intervalsSize; i++) {
        int preEnd = ret[*returnSize-1][1];
        int currStart = intervals[i][0];
        int currEnd = intervals[i][1];

        if(preEnd < currStart) {
            // 不重叠新增区间
            if(*returnSize >= size) {
                size += INCREASE;
                ret = realloc(ret, sizeof(int*)*size);
                if(!ret) exit(-1);
                *returnColumnSizes = realloc(*returnColumnSizes, sizeof(int)*size);
                if(!(*returnColumnSizes)) exit(-1);
            }
            tmp = malloc(sizeof(int)*2);
            if(!tmp) exit(-1);
            tmp[0] = currStart;
            tmp[1] = currEnd;
            ret[*returnSize] = tmp;
            (*returnColumnSizes)[*returnSize] = 2;
            (*returnSize)++;
        } else {
            // 重叠合并区间
            ret[*returnSize-1][1] = preEnd > currEnd ? preEnd : currEnd;
        }
    }

    return ret;
}

内容的提问来源于stack exchange，提问作者lxsolx