LeetCode 189 Rotate Array提交遇heap-buffer-overflow错误求修复

开发者阿泽

2026-8-14

解决LeetCode 189. 旋转数组时的堆缓冲区溢出问题

我正在解决LeetCode的189. 旋转数组问题：

给定一个数组，将数组向右旋转k步，其中k为非负整数。
示例1：
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转1步: [7,1,2,3,4,5,6]
向右旋转2步: [6,7,1,2,3,4,5]
向右旋转3步: [5,6,7,1,2,3,4]

我尝试用循环链表来解决该问题，代码如下：

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

// 链表节点结构
struct node {
    int info;
    struct node* next;
};

// 指向链表最后一个节点的指针
struct node* last = NULL;


void rotate(int* nums, int numsSize, int k){

  int i;
  struct node* temp;
    
  for (i = 0; i < numsSize; i++)
    {
      
    // 初始化新节点
    temp = (struct node*)malloc(sizeof(struct node));

    if (last == NULL) {
        temp->info = nums[i];
        temp->next = temp;
        last = temp;
    }

    else {
        temp->info = nums[i];
        temp->next = last->next;

        // 尾节点现在指向新节点temp
        last->next = temp;
    }
      
    }
    
  i=0;
  temp = (struct node*)malloc(sizeof(struct node));
  temp = last;

  while (i < k)
    {
      temp = temp->next;
      i++;
    }
    
  last = temp;
  temp = last->next;
  i=numsSize-1;
  
  // 旋转赋值
  do {
        printf("Data = %d\n", temp->info);
        nums[i]=temp->info;
        temp = temp->next;
        i--;
  } while (temp != last->next);

}

这段代码本地运行正常，所有测试用例都能得到正确结果，但提交到LeetCode时出现运行时错误：

heap-buffer-overflow

错误日志如下：

=================================================================
==31==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60200000022c at pc 0x55ee87988926 bp 0x7ffd33a4b650 sp 0x7ffd33a4b640
WRITE of size 4 at 0x60200000022c thread T0
    #2 0x7f79c721f0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
0x60200000022c is located 4 bytes to the left of 16-byte region [0x602000000230,0x602000000240)
allocated by thread T0 here:
    #0 0x7f79c7e64bc8 in malloc (/lib/x86_64-linux-gnu/libasan.so.5+0x10dbc8)
    #3 0x7f79c721f0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
Shadow bytes around the buggy address:
  0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff8000: fa fa 00 00 fa fa 00 00 fa fa 00 00 fa fa 00 00
  0x0c047fff8010: fa fa 00 00 fa fa 00 00 fa fa 00 00 fa fa fd fa
  0x0c047fff8020: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fa
  0x0c047fff8030: fa fa fd fa fa fa 00 00 fa fa fd fa fa fa fd fa
=>0x0c047fff8040: fa fa fd fa fa[fa]00 00 fa fa 00 00 fa fa 00 00
  0x0c047fff8050: fa fa 00 00 fa fa 00 00 fa fa fa fa fa fa fa fa
  0x0c047fff8060: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8070: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8080: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8090: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==31==ABORTING

问题原因及修复方案

1. 全局变量`last`未重置导致的污染问题

last是全局变量，LeetCode会多次调用rotate函数测试不同用例。第一次调用后last指向旧链表的尾节点，第二次调用时last不为空，会继续在旧链表后添加新节点，导致链表节点数量远超预期，后续访问时出现越界。

修复：在rotate函数开头重置last为NULL，同时释放上一次调用创建的链表节点，避免内存泄漏：

void rotate(int* nums, int numsSize, int k){
  // 释放上一次调用的链表
  if (last != NULL) {
      struct node* temp = last->next;
      struct node* nextNode;
      while (temp != last) {
          nextNode = temp->next;
          free(temp);
          temp = nextNode;
      }
      free(last);
      last = NULL;
  }

  // 后续代码保持不变...
}

2. 多余的malloc导致内存泄漏

代码中temp = (struct node*)malloc(sizeof(struct node));之后立刻将temp赋值为last，malloc的内存没有被释放，造成内存泄漏。虽然不是直接引发堆溢出的原因，但会引发内存问题，需要删除这行代码：

// 删掉这行多余的malloc
// temp = (struct node*)malloc(sizeof(struct node));
temp = last;

3. k大于数组长度的情况未处理

当k大于数组长度时，实际需要旋转的步数是k % numsSize，否则会出现循环遍历次数过多的情况。比如数组长度为7，k=10，实际只需要旋转3步。

修复：在使用k之前先处理：

k = k % numsSize;
if (k == 0) return; // 不需要旋转，直接返回

4. 数组赋值时的索引越界

赋值时从i = numsSize - 1开始递减，循环执行numsSize次后，i会变成-1，此时nums[i]会访问数组的负索引，这就是引发堆缓冲区溢出的直接原因。

原循环逻辑：

i=numsSize-1;
do {
    nums[i]=temp->info;
    temp = temp->next;
    i--;
} while (temp != last->next);

循环会执行numsSize次，最后一次赋值时i为-1，访问nums[-1]触发溢出。

修复：调整为从i=0开始递增的循环：

temp = last->next;
for (i = 0; i < numsSize; i++) {
    nums[i] = temp->info;
    temp = temp->next;
}

最终修复后的代码

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

struct node {
    int info;
    struct node* next;
};

struct node* last = NULL;


void rotate(int* nums, int numsSize, int k){
    // 处理空数组或无需旋转的情况
    if (numsSize <= 1 || k == 0) return;
    
    // 释放上一次调用的链表
    if (last != NULL) {
        struct node* temp = last->next;
        struct node* nextNode;
        while (temp != last) {
            nextNode = temp->next;
            free(temp);
            temp = nextNode;
        }
        free(last);
        last = NULL;
    }
    
    k = k % numsSize;
    if (k == 0) return;
    
    int i;
    struct node* temp;
    
    // 创建循环链表
    for (i = 0; i < numsSize; i++) {
        temp = (struct node*)malloc(sizeof(struct node));
        temp->info = nums[i];
        if (last == NULL) {
            temp->next = temp;
            last = temp;
        } else {
            temp->next = last->next;
            last->next = temp;
            last = temp;
        }
    }
    
    // 移动到旋转后的尾节点
    temp = last;
    for (i = 0; i < k; i++) {
        temp = temp->next;
    }
    last = temp;
    
    // 将链表值赋值回数组
    temp = last->next;
    for (i = 0; i < numsSize; i++) {
        nums[i] = temp->info;
        temp = temp->next;
    }
    
    // 释放链表，避免内存泄漏
    temp = last->next;
    struct node* nextNode;
    while (temp != last) {
        nextNode = temp->next;
        free(temp);
        temp = nextNode;
    }
    free(last);
    last = NULL;
}

内容的提问来源于stack exchange，提问作者Muhammed Ali SOYLU

LeetCode 189 Rotate Array提交遇heap-buffer-overflow错误求修复

示例1： #

问题原因及修复方案 #

1. 全局变量last未重置导致的污染问题 #

2. 多余的malloc导致内存泄漏 #

3. k大于数组长度的情况未处理 #

4. 数组赋值时的索引越界 #

最终修复后的代码 #