英文:
I am trying to store node pointers in a vector and I am having a heap-use-after-free error
问题
我在解决Leetcode问题 206. 反转链表:
> 给定一个单链表的头节点 head，反转该链表并返回反转后的链表。
以下是我的代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
vector<ListNode*> addrs;
ListNode* cur=head;
if(cur==NULL||cur->next==NULL) return cur;
// 将所有节点地址按顺序存储
while(cur!=NULL)
{
addrs.push_back(cur);
cur=cur->next;
}
// 反转过程
for(int i=addrs.size()-1;i>0;i--)
{
addrs[i]->next=addrs[i-1];
}
return addrs[addrs.size()-1];
}
};
当我在LeetCode上测试这段代码时，出现了以下错误：
> 错误: AddressSanitizer: 堆使用后释放
我猜测这个错误与向量有关。然而，我不明白为什么会出现这个错误。有人能帮我解释为什么会出现这个错误吗？
英文:
I am solving the Leetcode problem 206. Reverse Linked List:
> Given the head of a singly linked list, reverse the list, and return the reversed list.
Here is my code.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
vector<ListNode*> addrs;
ListNode* cur=head;
if(cur==NULL||cur->next==NULL) return cur;
// storing all addrs in sequence
while(cur!=NULL)
{
addrs.push_back(cur);
cur=cur->next;
}
// reversing process
for(int i=addrs.size()-1;i>0;i--)
{
addrs[i]->next=addrs[i-1];
}
return addrs[addrs.size()-1];
}
};
When I test the code at LeetCode, I get this error:
> ERROR: AddressSanitizer: heap-use-after-free
I am guessing that the error is related to the vector. However I don't get the exact reason why I have this error. Can someone help me why I am getting this error?
答案1
得分: 4
这个错误并不发生在你的代码中，而是发生在LeetCode平台在调用你的函数后执行的清理代码中。
更深层次的原因是你的函数没有设置原始头结点的 next 成员。这个节点已经成为了尾部，所以它的 next 成员应该更新为 nullptr，但你忘记了这样做。因此，你重连的链表没有终点。它在最后两个节点之间形成了一个循环。
因此，当LeetCode想要释放你的链表使用的内存时 -- 未料到它会有一个循环 -- 它会第二次访问一个节点并尝试再次释放它：这会触发异常。
解决方案很简单。在最终的 return 语句之前添加以下代码：
addrs[0]->next = nullptr;
注意，在你的代码中应该使用 nullptr 而不是 NULL。
另外，一个仍然存在的挑战是在不使用O(n)辅助内存的情况下解决这个练习，也就是说，不使用向量。只用几个指针变量是可以做到的。也许你想试一试...
英文:
This error does not occur in your code, but in the cleanup code that the LeetCode platform executes after having called your function.
The deeper cause is that your function does not set the next member of the original head node. This node has become the tail and so its next member should be updated to nullptr, which you forgot to do. By consequence your rewired linked list has no end. It has a cycle between its last two nodes.
And so when LeetCode wants to free up the memory used by your linked list -- not expecting it to have a cycle -- it will visit a node for a second time and try to free it again: this triggers the exception.
The solution is simple. Add this code just before the final return statement:
addrs[0]->next = nullptr;
Note that you should use nullptr in your code instead of NULL.
Also, a remaining challenge is to solve this exercise without O(n) auxiliary memory, i.e. without the vector. It is possible to do with just a few pointer variables. Maybe you want to try that...
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论