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;
        }
    }
}

CodePudding user response：

Try This

Explanation : So we are receiving head of the Circular Linked List and taking a curr pointer and pointing it to the head of the CLL. Then we are taking another pointer and keeping it one step before the curr pointer so that we can point that pointer's next(prev->next) to curr's next(curr->next) and free the curr node.

void deleteTail(Node* &head)
{
Node* curr = head;
Node* prev = NULL;
while(curr->next != head)
{
    prev = curr;
    curr = curr->next;
}
prev->next = curr->next;
curr->next = NULL;
delete curr;

CodePudding user response：

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;
        }
    }
}