1

我正在编写 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 没有捕捉到“heap-use-after-free”错误？

4

2 回答 2

5

根本问题

至少从外观上看，问题在于您未能正确终止您的链表。

您从单个链表开始，并将其分成奇数和偶数部分就好了。

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

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

因此，对于 5 元素列表，您将得到如下信息：

在此处输入图像描述

显然，当你把这两个部分放在一起时last_odd->next = even_head;，你需要添加类似last_even->next = nullptr;这样的东西，这样串联的列表就会被终止。

区别

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

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

于 2020-12-27T09:36:58.843 回答
1

您在 C++ 程序中可能做错的大多数事情都属于未定义行为的范畴。在释放后使用内存、取消引用空指针、读取未初始化的变量、读取或写入超出数组边界，所有这些都会调用未定义的行为。

未定义的行为意味着 C++ 标准不需要受影响程序的任何特定行为。产生错误消息、抛出异常、正常工作和崩溃都是允许的行为（就像其他任何事情一样）。因此，MSVS 没有产生任何类型的错误并没有错。

尤其是初学者有时很难处理未定义的行为，但是当他们解决哲学问题时，这个概念本身就很简单。

C++ 有未定义行为概念的原因也很简单。检查错误需要时间。即使没有发生错误，检测到错误的代码也会比没有检测到错误的代码运行得更慢。未定义的行为允许编译器编写者不检查错误，从而生成更快的代码。

现在检查错误显然很有用，尤其是对于调试。因此，大多数编译器都有各种选项可以检测到一些错误。作为在线法官运行的编译器会尽可能高地显示错误检测是有道理的。

于 2020-12-27T07:01:18.363 回答