# Delete Last Occurrence

Difficulty Level Easy

## Problem Statement

In the “Delete Last Occurrence” problem we have given a linked list. Write a program to delete the last occurrence of a given key from the linked list. The list can contain duplicates.

## Example

`1  2  3  5  2  10`
`1  2  3  5  2`

## Approach

Given a linked list that may contain duplicate items, we have to delete the last occurrence of an element.

The basic intuition behind this problem is that we can store the previous node pointer and the current node pointer whenever the current node value is equal to the value of the key_item( the last occurrence of which we have to delete).

So, after iterating the whole linked list we have the previous node pointer and the current node pointer of the node which we have to delete. So what we do is, we replace the previous next pointer with the current next pointer. And we deleted the last occurrence of the item.

First, we take a node pointer which stores the head pointer, and two other pointers prev and curr,  which store the previous node and the current node pointers. Then we iterate the linked list, whenever the curr next value equals the value of key element we store prev to the node value and curr to node next. And we point node to node next. When we iterate the whole linked list then we replace the prev next to curr next.

And if the prev pointer value is null and the head value is equal to the key, then we replace the head to head next pointer. Since the head is the first and last occurrence of the key.

## Implementation

### C++ Program for Delete Last Occurrence

```#include<bits/stdc++.h>
using namespace std;

public:
struct ListNode {
ListNode *next;
int val;
ListNode(int a): next(NULL), val(a){}
};

}

ListNode *node = new ListNode(val);
}

void DeleteLastOccurenceOfKey(int key){
ListNode* prev = NULL,*curr=NULL;
while(node){
if(node->next && node->next->val==key){
prev = node;
curr = node->next;
}
node = node->next;
}
if(prev){
prev->next = curr->next;
}
}

void print_list(){
while(node){
cout<<node->val<<" ";
node = node->next;
}
cout<<endl;
}
};

int main(){

list->print_list();

list->DeleteLastOccurenceOfKey(5);
list->print_list();
list->DeleteLastOccurenceOfKey(1);
list->print_list();
}```

### Java Program for Delete Last Occurrence

```import java.util.*;
import java.lang.*;
import java.io.*;

public class Main{

public static void main (String[] args) throws java.lang.Exception{

obj.printList();
obj.DeleteLastOccurenceOfKey(5);
obj.printList();
obj.DeleteLastOccurenceOfKey(1);
obj.printList();

}

class Node{
Node next = null;
int val = 0;

public Node(int val){
this.val = val;
}
}

private int size;

this.size = 0;
}

Node node = new Node(val);
if(this.size == 0){
}
else{
}
this.size++;
}

public void DeleteLastOccurenceOfKey(int key) {
Node prev=null;
Node curr=null;

while(node!=null){
if(node.next!=null && node.next.val==key){
prev=node;
curr=node.next;
}
node=node.next;
}
if(prev!=null){
prev.next=curr.next;
}
}

public void printList(){
while(curr!=null){
System.out.print(curr.val+" ");
curr = curr.next;
}
System.out.println("");
}

}
}```
```1 2 3 4 5
1 2 3 4
2 3 4```

## Complexity Analysis for Delete Last Occurrence

### Time Complexity

O(n) where n is the number of nodes present in the linked list. Here we traverse the linked list till we get the desire node which take linear time.

### Space Complexity

O(1) because we don’t use any auxiliary space here.

Translate »