c++: double free or corruption (fasttop)

Question

I am trying to find the node where the cycle begins in the list. The result returned is correct. However, an error stating * Error in ./solution: double free or corruption (fasttop): 0x0000000000b3e030 Aborted is shown. I saw some other similar problems, and I think the problem is with temp1=temp;. But I don't know how to solve this problem. How to correct it? Also why is this error occurring?

ListNode* Solution::detectCycle(ListNode* A) {
    ListNode* temp = A;
    ListNode* temp1 = A;

    while(temp->next!=NULL && temp->next->next!=A->next ){

        temp1 = temp;
        temp = temp->next;
        temp1->next=A->next;
    }
    if(temp->next==NULL) {
        temp->val=-1;
        delete temp1;
        return temp;

    }
    else {
        temp= temp->next;
        delete temp1;

        return temp;
    }

}

Thank you.

Answer 1

As a direct answer, your code is crashing because your are accessing nodes that are already free. Beyond accessing, you are deleting a node that has already been deleted. This 'double free' will almost alway result in a crash or other chaos. A strong understanding of heap mechanics in C/C++ will save you a lot of misery, it is worth studying.

I'm not too sure what the requirements are but I believe your are trying to check for a circular linked list. I not clear why you are deleting any of the nodes in a 'detect' method. Are you trying to break the loop? If so, all of the node will still be in the list so nothing will be deleted, just change the ->next to nullptr on the node that loops back.

Here is some example code from your original. I created it using your code as a base and then using the gdb debugger to debug it. An effective software engineer is a master of the debugger, embrace it. It is a Minimal, Complete and Verifiable example as described in the comments.

I put a few tests as an example of 'use cases', no loop, degenerate loop, longer loop. As software engineers, a big part of our job is thinking about error cases which often occur on the boundaries. There may be others that I have not covered.

As noted in the comments, compiling or a single successful use case doesn't indicate defect free software. Rigorous testing is needed to gain confidence. This kind of testing is often referred to as 'unit testing' there is a large body of literature on the subject.

#include <iostream>

struct ListNode
{
  int val;
  ListNode* next;
};

//Look for a loop back to A

ListNode* detectCycle(ListNode* A) {
    if(A == nullptr)  // can't be a loop if list is empty
        return nullptr;

    ListNode* temp = A;


    while(temp->next!=NULL && temp->next !=A ){
        temp = temp->next;
    }
    if(temp->next==NULL) {
        return nullptr; // No loop

    }
    else {
        return temp; // Node where loop starts, may be A itself
    }

}

int main(int argc,char* arv[])
{
   ListNode *a = new ListNode;
   ListNode *loop = nullptr;
   loop = detectCycle(a);
   if(loop == nullptr) 
     std::cout << "Case 1 passed" << std::endl;
   a->next = a;
   loop = detectCycle(a);
   if(loop == a) 
     std::cout << "Case 2 passed" << std::endl;
   ListNode *b = new ListNode;
   ListNode *c = new ListNode;
   ListNode *d = new ListNode;
   a->next = b;
   b->next = c;
   c->next = d;
   d->next = a;
   loop = detectCycle(a);
   if(loop == d) 
     std::cout << "Case 3 passed" << std::endl;
   loop = detectCycle(b);
   if(loop == a) 
     std::cout << "Case 4 passed" << std::endl;

   return 0;
}