Below program is used to remove the duplicates from a sorted singly linked list. The code gives garbage values in online IDE. But when I comment the line .
delete curr;
The program works fine in online IDE itself. Here is the function I wrote. The other parts of the code are well-defined(not by me) by the online Judge.
And also the code without commenting the line delete curr; works fine in local IDE(codeblocks).
FULL PROGRAM:http://ideone.com/9bHab0
Why do I get the garbage values?
Node *removeDuplicates(Node *root)
{
// your code goes here
struct Node* curr = root,*prev = NULL;
while(curr)
{
if(prev==NULL)
prev = curr;
else if(curr->data!=prev->data)
prev = curr;
else
{
prev->next = curr->next;
delete curr;
curr = prev->next;
}
}
return root;
}
EDIT: One could see the pointer whose location is deleted, is reassigned immediately. Thus there couldn't be a dangling pointer here!
Lets take a very simple example, with a two-node list, where you have e.g.
node1 -> node2
With the first iteration then prev is NULL so you do prev = curr. Now curr and prev points to the same node.
That means in the second iteration both if conditions are false (prev != NULL and curr->data == prev->data) you go into the else part, where you have
prev->next = curr->next;
delete curr;
curr = prev->next;
Here you delete curr but curr is pointing to the same memory as prev, leading to undefined behavior in the assignment curr = prev->next, as you now dereference the stray pointer prev.
To make matters worse, you then enter a third iteration where prev is still pointing to the deleted first node, and again dereference the invalid prev pointer (in your second if condition) and you once again end up in the else part where you continue the invalid dereferencing. And so on in infinity (or you get a crash).