"Heap use after free" error in LeetCode Online Judge but not Visual Studio

user_14091616 0
Viewed 3374

I am coding a solution to the LeetCode problem "Odd Even Linked List" which can be read here.

My code is failing the test case with the error

================================================================
==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

However, when I run the code in Visual Studio to diagnose the error, everything works. The solution for LeetCode is here:

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

The code I am using to test the above is here:

#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;
}

If you wish to test this, you will want the definition of a ListNode which is here:

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

Because the code works on my compiler, I am having trouble diagnosing the error. While of course I hope someone can identify the error, my question is this: why is MSVS not catching the "heap-use-after-free" error?

heap-memory pointers visual-c++ c++
2 Answers

Underlying Problem

At least from the looks of things, the problem is that you're failing to terminate your linked list correctly.

You're starting with a single linked list, and separating it into odd and even pieces just fine.

Then at the end, you (correctly) concatenate the evens list to the end of the odds list.

But then you missed one point: the last node in the evens list (at least potentially) has a non-null next pointer. Specifically, if the last element of the list was an odd element, that last even element will still have a pointer to the last odd element.

So for a 5 element list you'll get something like this:

enter image description here

Obviously, when you put the two pieces together, after the last_odd->next = even_head;, you need to add something like last_even->next = nullptr; so the concatenated list will be terminated.

The Difference

In the code you've shown above, you start by allocating five nodes, and then finish by deleting exactly the same five nodes, ignoring the structure of the linked list.

But the online judge apparently walks through the linked list, and deletes nodes as it gets to them in the linked list. So, when it walks through the linked list you returned, after it gets to the last node, it follows the non-null next pointer to the last odd node, and tries to delete it--but since it's already been deleted, an error is generated.

user_1799100

Most things that you can do wrong in a C++ program fall into the category of undefined behaviour. Using memory after is has been freed, dereferencing a null pointer, reading an uninitialised variable, reading or writing beyond the bounds of an array, all of these invoke undefined behaviour.

Undefined behaviour means that the C++ standard does not require any particular behaviour from an affected program. Producing an error message, throwing an exception, working apparently normally and crashing are all permitted behaviours (as is anything else). So it's not wrong that MSVS did not produce any kind of error.

Beginners especially sometimes have a hard time with undefined behaviour, but when they do its a philosophical problem, the concept itself is quite simple.

The reason that C++ has the concept of undefined behaviour is also simple. Checking for errors takes time. Code that detects errors will run slower than code that doesn't even if the errors don't occur. Undefined behaviour permits compiler writers not to check for errors and therefore to produce faster code.

Now checking for errors is obviously useful, especially for debugging. So most compilers have various options whereby some errors are detected. It makes sense that a compiler running as an online judge would have the error detection turned up as high as possible.

user_8820030
Related