Delete last occurrence

In the given linked list, write a function to delete the last occurrence of a given key from the linked list. The list can contain duplicates.

Example

Time complexity : O(n)

Algorithm

a. Traverse in the linked list start from the head and check if next of current has the value.

b. If yes store it and move forward to find any other occurrences. If found any update the one already stored.

c. After reaching the end, delete the stored.

d. Delete last occurrence by copying data of next node and deleting the head node.

Algorithm working

C++ Program

#include <bits/stdc++.h>

using namespace std;

struct LLNode
{
    int data;
    struct LLNode* next;
};

/* Function to insertAtBeginning a node */
void insertAtBeginning(struct LLNode** head, int dataToBeInserted)
{
    struct LLNode* curr = new LLNode;
    curr->data = dataToBeInserted;
    curr->next = NULL;    
    if(*head == NULL)
            *head=curr; //If this is first node make this as head of list
        
    else
        {
            curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
            *head=curr;
        }
        
        //O(1) constant time
}
 
//display linked list
void display(struct LLNode**head)
{
    struct LLNode *temp= *head;
    while(temp!=NULL)
        {
            if(temp->next!=NULL)
            {
                cout<<temp->data<<"->";
            }
            else
            {
                cout<<temp->data;
            }
            temp=temp->next; //move to next node
        }
        //O(number of nodes)
    cout<<endl;
}
 
void deleteLast(struct LLNode** head, int key)
{
    // Initialize previous of LLNode to be deleted
    struct LLNode* x = NULL;
    struct LLNode* temp = *head;
    //update x if key is found.
    //move forward till the end.
    //start from head
    while(temp)
    {
        if(temp->next && temp->next->data == key)
        {
            x = temp;
        }
        temp = temp->next;
    }
    //key occurs atleast once except head node
    if(x)
    {
        //delete x by copying of next to it.
        //delete next
        temp = x->next;
        x->next = x->next->next;
        delete temp;
    }
    //key occurs at head
    else
    {
        if (*head && (*head)->data == key )
        {
             struct LLNode * temp = *head;
            *head =  (*head)->next;
            delete temp;
        }
    }
}//Main function
int main()
{
   
    struct LLNode* head = NULL;//Initial list has no elements
    insertAtBeginning(&head, 9);
    insertAtBeginning(&head, 8);
    insertAtBeginning(&head, 3);
    insertAtBeginning(&head, 6);
    insertAtBeginning(&head, 5);
    insertAtBeginning(&head, 4);
    insertAtBeginning(&head, 3);
    insertAtBeginning(&head, 2);
    insertAtBeginning(&head, 1);           
   
    cout<<"Input linked is: ";
    display(&head);
    int k;
    cout<<"Enter key whose last occurrence to be deleted: ";
    cin>>k;
    cout<<"\ndeleting....."<<k;
    deleteLast(&head, k);
    cout<<"\nOutput linked list: ";   
    display(&head);
    return 0;
}
Try It

 


Next > < Prev
Scroll to Top