c++linked-listcircular-list

How to delete "end" node from a circular linked list using only tail in c++?


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

Solution

  • There are several issues with your deleteEnd function:

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