# Delete last occurrence

0
341

## 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.

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

//O(1) constant time
}

{
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;
//update x if key is found.
//move forward till the end.
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;
}
else
{
{
struct LLNode * temp = *head;
delete temp;
}
}
}//Main function
int main()
{

struct LLNode* head = NULL;//Initial list has no elements

int k;
cout<<"Enter key whose last occurrence to be deleted: ";
cin>>k;
cout<<"\ndeleting....."<<k;