LeetCode 23题合并K个升序链表：指针返回错误排查求助

问题描述 #

我在解决LeetCode第23题《合并K个升序链表》时，遇到了指针返回处理的问题。本地运行代码无报错且结果正确，但在LeetCode平台上触发AddressSanitizer堆缓冲区溢出错误，哪怕仅返回lists[0]也会报错。怀疑是指针返回方式有误，请求排查。

原实现代码 #

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode node;

void printList(node *root) {
    printf("Printing list: ");
    node *temp = root;
    while (temp) {
        printf(" %d ,", temp->val);
        temp = temp->next;
    }
}

void mergeList(node **root_a, node *root_b) {
    printf("\nA--");
    printList(*root_a);
    printf("\nB--");
    printList(root_b);

    node *temp;

    if ((*root_a)->val < root_b->val) {
        printf("\nChoosing a as root\n");
        temp = *root_a;
        *root_a = (*root_a)->next;
    } else {
        printf("\nChoosing b as root\n");
        temp = root_b;
        root_b = root_b->next;
    }

    node *output = temp;

    printf("ROOT: %b ", temp->val);
    while (*root_a && root_b) {
        if ((*root_a)->val <= root_b->val) {
            printf(" a");
            temp->next = *root_a;
            temp = *root_a;
            *root_a = (*root_a)->next;
        } else {
            printf(" b");
            temp->next = root_b;
            temp = root_b;
            root_b = root_b->next;
        }
        printf(" %d ", temp->val);
    }

    printf("\n");
    if (*root_a) {
        printf("\nFinishing with a [%d]\n", (*root_a)->val);
        temp->next = *root_a;
    } else if (root_b) {
        printf("\nFinishsing with b [%d]\n", root_b->val);
        temp->next = root_b;
    }
    printf("RESULT: ");
    *root_a = output;
    printList(*root_a);
}

struct ListNode *mergeKLists(struct ListNode **lists, int listsSize) {
    node *root = lists[0];
    for (int i = 1; i < listsSize; i++) {
        printf("\nStarting merge");
        mergeList(&root, lists[i]);
        printf(" >>> ");
        printList(root);
        printf("Finished merging\n");
    }

    printList(lists[0]);
    printList(root);
    return lists[0]; 
}

错误日志 #

=================================================================
==23==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6020000001b0 at pc 0x55a0dec96f4d bp 0x7fff5e6d8870 sp 0x7fff5e6d8860
READ of size 8 at 0x6020000001b0 thread T0
    #1 0x7f5048e0bd8f  (/lib/x86_64-linux-gnu/libc.so.6+0x29d8f)
    #2 0x7f5048e0be3f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x29e3f)
0x6020000001b1 is located 0 bytes to the right of 1-byte region [0x6020000001b0,0x6020000001b1)
allocated by thread T0 here:
    #0 0x7f50497db887 in __interceptor_malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:145
    #3 0x7f5048e0bd8f  (/lib/x86_64-linux-gnu/libc.so.6+0x29d8f)
Shadow bytes around the buggy address:
  0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff8000: fa fa fd fa fa fa 00 00 fa fa 00 00 fa fa 00 00
  0x0c047fff8010: fa fa fd fa fa fa 00 00 fa fa 00 00 fa fa 00 00
  0x0c047fff8020: fa fa fd fa fa fa 00 00 fa fa 00 00 fa fa fd fa
→0x0c047fff8030: fa fa 00 fa fa fa[01]fa fa fa fa fa fa fa fa fa
  0x0c047fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8050: fa fa fa fa fa fa fa fa 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
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
==23==ABORTING

核心问题分析 #

1. 空链表/空输入未处理：当listsSize=0时，访问lists[0]属于非法内存访问；当链表数组中存在空指针（空链表）时，mergeList直接解引用(*root_a)->val或root_b->val会触发空指针越界，这是堆溢出的直接原因。
2. 返回值指向错误：mergeKLists最终返回lists[0]，但合并过程中lists[0]的指针已经被mergeList修改（通过*root_a = (*root_a)->next），导致返回的指针指向已失效的内存区域。
3. 格式符错误：printf("ROOT: %b ", temp->val);中的%b不是标准整数格式符，会导致输出乱码，甚至可能引发额外的内存异常。

修复后的代码 #

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode node;

// 合并两个有序链表的辅助函数
node* mergeTwoLists(node* l1, node* l2) {
    // 哨兵节点简化边界处理
    node dummy;
    node* tail = &dummy;
    dummy.next = NULL;
    
    while (l1 && l2) {
        if (l1->val <= l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    
    // 拼接剩余未处理的节点
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}

struct ListNode *mergeKLists(struct ListNode **lists, int listsSize) {
    // 处理空输入情况
    if (listsSize == 0) return NULL;
    
    node* result = lists[0];
    for (int i = 1; i < listsSize; i++) {
        // 自动处理空链表合并
        result = mergeTwoLists(result, lists[i]);
    }
    
    return result;
}

修复说明 #

• 新增边界处理：直接处理listsSize=0的空输入场景，避免非法内存访问；mergeTwoLists自动兼容空链表合并，无需额外判断。
• 改用哨兵节点：简化链表头节点的选择逻辑，减少指针操作错误，避免手动调整原链表指针导致的内存混乱。
• 修正返回值：返回合并后的result指针，确保指向正确的链表头节点。
• 移除调试代码：LeetCode平台上调试打印可能干扰内存检测，同时解决了格式符错误的问题。

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