I am trying to store node pointers in a vector and I am having a heap-use-after-free error

Question

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?

Answer 1

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