1 相关标签
链表、双指针、C 语言
2 报错情况
2.1 题目
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
2.2 错误代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
int distance = 0; // 计数器
struct ListNode *end = head, *del = head, *beforedel = head;
// 定位删除的节点
while(end){
if(distance < n){
++distance;
}
else{
beforedel = del; // 定位删除节点前的节点
del = del->next;
}
end = end->next;
}
// 删除节点
beforedel->next = beforedel->next->next;
free(del);
return head;
}
2.3 测试用例
[1]
1
2.4 报错内容
runtime error: member access within null pointer of type 'struct ListNode' [solution.c]
在struct ListNode类型的空指针中访问成员
3 Debug思路
3.1 排查出错原因
运行原有示例中的其他两组
[1,2,3,4,5]
2
[1,2]
1
均输出正确结果。
[1,2,3,5]
[1]
猜测是删除了第1个节点引发的报错，更改示例如下
[1,2,3,4,5]
5
[1,2]
2
运行后出现新的报错
=================================================================
==43==ERROR: AddressSanitizer: heap-use-after-free on address 0x602000000030 at pc 0x55fd91f42904 bp 0x7ffe184c15b0 sp 0x7ffe184c15a0
READ of size 4 at 0x602000000030 thread T0
#2 0x7f9486376082 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x24082)
0x602000000030 is located 0 bytes inside of 16-byte region [0x602000000030,0x602000000040)
freed by thread T0 here:
#0 0x7f9486fbe40f in __interceptor_free ../../../../src/libsanitizer/asan/asan_malloc_linux.cc:122
#2 0x7f9486376082 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x24082)
previously allocated by thread T0 here:
#0 0x7f9486fbea06 in __interceptor_calloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cc:153
#4 0x7f9486376082 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x24082)
Shadow bytes around the buggy address:
0x0c047fff7fb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
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 fd fa fa[fd]fd fa fa 00 00 fa fa 00 00
0x0c047fff8010: fa fa 00 00 fa fa 00 00 fa fa 04 fa fa fa fa fa
0x0c047fff8020: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8030: fa fa fa fa fa fa fa 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
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
==43==ABORTING
注释掉 free(del); 后再运行，输出错误结果
[1,3,4,5]
预期结果：[2,3,4,5]
[1]
预期结果：[2]
显然猜测正确
参考力扣官方给出的题解，前言中提到“头节点不存在前驱节点，需要在删除头节点时进行特殊判断”，这类题目通常做法是在头节点前“添加一个哑节点（dummy node）”，再参考力扣的视频题解得知，该题给出的链表不设置空的头节点，链表的头节点中直接存放第一个元素
而错误代码编写时将链表的头节点作为一个空节点计算，代码在删除链表倒数第 n 个节点时删除的是第 2 个节点（如上图存放 2 的节点），而执行 free(del) 后又将第一个节点（head）的内存释放掉，使得返回的头节点为已被释放掉的内存，导致报错
3.2 寻求解决方法
由于头节点不存在前驱节点，仅存在指向头节点的指针，因此需要对删除头节点的情况进行特殊判断
// 删除节点
if(beforedel == del){
head = del -> next; // del -> next 或 beforedel -> next 均可
}
else{
beforedel -> next = beforedel -> next -> next;
}
free(del);
输出正确结果
开销
4 最终结果
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
int distance = 0; // 计数器
struct ListNode *end = head, *del = head, *beforedel = head;
// 定位删除的节点
while(end){
if(distance < n){
++distance;
}
else{
beforedel = del; // 定位删除节点前的节点
del = del->next;
}
end = end->next;
}
// 删除节点
if(beforedel == del){
head = del -> next; // del -> next 或 beforedel -> next 均可
}
else{
beforedel -> next = beforedel -> next -> next;
}
free(del);
return head;
}
5 总结
删除链表节点问题需要先确定给出链表的头节点是否存放了数据。对于头节点中存在数据的链表，需要另外考虑删除头节点的情况
官方题解采用添加哑节点的方法能让过程更简洁一些，在内存消耗方面也更占优势
