Delete Last Occurrence

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;

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

    MyLinkedList():head(NULL) {
    }
    
    void addAtHead(int val) {
        ListNode *node = new ListNode(val);
        node->next = head;
        head = node;
    }
    
    void DeleteLastOccurenceOfKey(int key){
    	ListNode* node = head;
    	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;
    	}else if(head->val==key){
    		head = head->next;
    	}
    }

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

int main(){
  MyLinkedList *list = new MyLinkedList();
  list->addAtHead(5);
  list->addAtHead(4);
  list->addAtHead(3);
  list->addAtHead(2);
  list->addAtHead(1);
  
  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{
    
    MyLinkedList obj = new MyLinkedList();
    obj.addAtHead(5);
    obj.addAtHead(4);
    obj.addAtHead(3);
    obj.addAtHead(2);
    obj.addAtHead(1);
    
    obj.printList();
    obj.DeleteLastOccurenceOfKey(5);
    obj.printList();
    obj.DeleteLastOccurenceOfKey(1);
    obj.printList();
    
  }
  
  public static class MyLinkedList {
    
      class Node{
          Node next = null;
          int val = 0;
          
          public Node(int val){
              this.val = val;
          }
      }
      
      private Node head;
      private int size;

      public MyLinkedList() {
          this.head = null;
          this.size = 0;
      }
      
      
      public void addAtHead(int val) {
          Node node = new Node(val);
          if(this.size == 0){
              this.head = node;
          }
          else{
              node.next = this.head;
              this.head = node;
          }
          this.size++;
      }
      
    public void DeleteLastOccurenceOfKey(int key) {
        Node node=head;
        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;
        }else if(head.val == key){
        	head = head.next;
        }
    }

    public void printList(){
      Node curr = head;
      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.