LeetCode Online Judge 中出现“释放后堆使用”错误，但 Visual Studio 中没有

Question

我正在编写 LeetCode 问题“奇偶链表”的解决方案，可以在此处阅读。

我的代码未通过测试用例并出现错误

================================================================
==31==ERROR: AddressSanitizer: heap-use-after-free on address 0x6020000000d8 at pc 0x0000003d7f1d bp 0x7fff37cf9640 sp 0x7fff37cf9638
READ of size 8 at 0x6020000000d8 thread T0

但是，当我在 Visual Studio 中运行代码来诊断错误时，一切正常。LeetCode的解决方案在这里：

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        
        if (!head){
            return head;
        }
        
        ListNode* odd_head = head;
        ListNode* even_head = odd_head->next;
        
        if (!even_head){
            return head;
        }
        
        ListNode* last_odd = odd_head;
        ListNode* last_even = even_head;
        ListNode* next_node = even_head->next;
        
        bool flag = true;
        
        while(true){
            if (!next_node){
                break;
            }
            if (flag){
                last_odd -> next = next_node;
                last_odd = next_node;
            } else {
                last_even -> next = next_node;
                last_even = next_node;
            }
            
            flag = !flag;
            
            next_node = (next_node->next);
            
        }
        last_odd->next = even_head;
        
        return odd_head;
    }
};

我用来测试上述内容的代码在这里：

#include "oddevenlinkedlist.h"

#include <iostream>
int main() {

    ListNode* l1 = new ListNode(1);
    ListNode* l2 = new ListNode(2);
    l1->next = l2;
    ListNode* l3 = new ListNode(3);
    l2->next = l3;
    ListNode* l4 = new ListNode(4);
    l3->next = l4;
    ListNode* l5 = new ListNode(5);
    l4->next = l5;

    Solution solution{};
    ListNode* result = solution.oddEvenList(l1);
    ListNode* next_node = result;
    for (int i = 0; i < 5; ++i) {
        std::cout << next_node->val << " ";
        next_node = next_node->next;
    }

    delete l1;
    delete l2;
    delete l3;
    delete l4;
    delete l5;

    return 0;
}

如果您想测试这一点，您将需要ListNode此处的 a 定义：

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) {}
    
};

由于代码可以在我的编译器上运行，因此我无法诊断错误。当然，我希望有人能够识别该错误，但我的问题是：为什么 MSVS 没有捕获“释放后堆使用”错误？

Answer 1

根本问题

至少从表面上看，问题在于您未能正确终止链接列表。

您从一个链表开始，然后将其分成奇数和偶数部分就可以了。

然后最后，您（正确地）将evens列表连接到列表的末尾odds。

但是你错过了一点：列表中的最后一个节点evens（至少可能）有一个非空next指针。具体来说，如果列表的最后一个元素是奇数元素，则最后一个偶数元素仍将具有指向最后一个奇数元素的指针。

因此，对于 5 元素列表，您将得到如下所示的内容：

显然，当您将两个部分放在一起时，在 后面last_odd->next = even_head;，您需要添加类似的内容last_even->next = nullptr;，以便终止串联列表。

区别

在上面显示的代码中，首先分配五个节点，然后通过删除完全相同的五个节点来完成，忽略链表的结构。

但在线法官显然会遍历链表，并在到达链表中的节点时删除它们。因此，当它遍历您返回的链表时，在到达最后一个节点后，它会跟随非空的 next 指针指向最后一个odd节点，并尝试删除它 - 但由于它已经被删除，所以会出现错误生成的。