I need to write three separate functions for node deletion in a circular singly linked list (deleteFront(), deleteMiddle() and deleteEnd()). I have to use only tail (last). For some reason, my deleteEnd() function deletes second to the last node. Can anyone please help?
struct node
{
int data;
struct node* next;
};
// some other functions
// 6 -> 5 -> 4 -> 3 -> deleteEnd() does 6 -> 5 -> 3 ->
void deleteEnd(struct node* last)
{
if (last != NULL)
{
if (last->next == last)
last = NULL;
else
{
node* temp = NULL;
node* temp1 = last;
while (temp1->next != last)
{
temp = temp1;
temp1 = temp1->next;
}
temp->next = temp1->next;
delete temp1;
}
}
}
There are several issues with your deleteEnd
function:
There is no way that the caller can get the new tail
reference, because the tail
argument is passed by value. The tail
parameter should be a pass-by-reference parameter.
The statement after the loop (in the else
block) does not remove the correct node. After the loop, temp1->next
will be equal to last
, and it should be that node that is removed, yet your code removes temp1
. You can fix this by changing the loop condition and initialise the temp
and temp1
variables to point to one node further in the list.
The else
block does not update tail
, yet it is clear that it should, since the original tail
node is deleted.
Less of an issue, but in C++ you should not use NULL
, but nullptr
.
Here is a correction:
void deleteEnd(struct node* &last) // corrected
{
if (last != nullptr)
{
if (last->next == last)
last = nullptr;
else
{
node* temp = last; // corrected
node* temp1 = last->next; // corrected
while (temp1 != last) // corrected
{
temp = temp1;
temp1 = temp1->next;
}
last = temp; // added
temp->next = temp1->next;
delete temp1;
}
}
}