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

Question

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?

Answer 1

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:

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.