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.


Time complexity : O(n)


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
            curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
        //O(1) constant time
//display linked list
void display(struct LLNode**head)
    struct LLNode *temp= *head;
            temp=temp->next; //move to next node
        //O(number of nodes)
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
        if(temp->next && temp->next->data == key)
            x = temp;
        temp = temp->next;
    //key occurs atleast once except head node
        //delete x by copying of next to it.
        //delete next
        temp = x->next;
        x->next = x->next->next;
        delete temp;
    //key occurs at head
        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: ";
    int k;
    cout<<"Enter key whose last occurrence to be deleted: ";
    deleteLast(&head, k);
    cout<<"\nOutput linked list: ";   
    return 0;


Leave a Comment

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions