Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach
4.
Algorithm
5.
Java Implementation
5.1.
Output
5.2.
Complexity Analysis
6.
Frequently Asked Questions
6.1.
How do you remove the last element in a linked list in Java?
6.2.
How to remove an item from a Linked List?
6.3.
How do you remove the last element in a linked list Python?
6.4.
 How to find the last node in a Linked list?
6.5.
 When some node is deleted from the linked list, what happens?
7.
Conclusion
Last Updated: Mar 27, 2024

Delete the last occurrence of an item from Linked List

Author Manvi Chaddha
1 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Linked Lists are an important part of all the coding interviews, be it online tests or in-person interviews; there are high chances that questions related to Linked List will be asked. One important question is, " Delete the Last occurrence of an item from Linked List." It's highly recommended to pause for a moment and figure out how to approach this problem independently.

Problem Statement

The problem statement on hand says, "Given a singly linked list of integers, your task is to delete the last occurrence of an element x in the Linked List ."Let's look at some examples to understand this:

Example 1:

Linked List : 1->2->3->4->5->2->1->NULL 
The element x is 2

The Linked List, after deletion of the last occurrence of 2, becomes 
1->2->3->4->5->1->NULL

Example 2:

Linked list: 0->3->0->8->2->0->0->0->NULL 
The element x is 0 

The Linked List after deletion of the last occurrence of 0 becomes 
0->3->0->8->2->0->0->NULL

In an interview, it's recommended that before jumping to the solution, first of all, ask some clarifying questions to the interviewer; for example, In this question, some clarifying questions could be:

Q1) What if the item x only occurs once in the Linked List? 
Q2) What if the element whose last occurrence is to be deleted is not present in the Linked List? 

The answer to question 1 will be to delete the first occurrence of x, as x occurs only once, which will be the first and last occurrence of x. The answer to question 2 is to print a message saying that Node is not present in the Linked list and return the original linked list. Some other questions may be related to the input size and whether you can include extra space or not. Asking such questions in an interview will help the interviewer understand your thought process and leave a good impression. 

Approach

Whenever you cannot think of a solution, try to develop the brute force solution. On a rough level, think about what could be done to get a working solution for the problem.  
In a nutshell, we require the following steps:

  • Traversing the Linked List
  • For each node, check if the node's data is x.
    • If the node's data is x, it may or may not be deleted.
      • The node will be deleted if this is the last occurrence of x.
      • Otherwise, the node will not be deleted.
  • If the entire linked list is traversed and still we have not found the node with value x, then that means the node is not present in the linked list. 

The only tricky part of this question is how will you figure out that the current occurrence of element x is the last occurrence of x??

(Source: giphy.com)

The idea is simple, for every occurrence of x, consider that this is the last occurrence of x. You can maintain a special pointer that will initially point to the head of the linked list; now, when traversing the linked list, whenever you find a node whose value is equal to x, move the special pointer to that position. Let’s take an example to better understand this, consider a linked list of 8 elements, 0->3->0->8->2->0->0->0->NULL. 
The ptrX is initially pointing to the first element in the Linked List. The linked list will be linearly traversed by one node, and for every node, we will check if the data of the current node is equal to x; if the data equals x, then move the ptrX to that position as shown below:

The current node data is 3, which is not equal to x, so that the ptrX will remain unchanged.

The current node’s data is 0, equal to x, so the ptrX will now point to this node.

The current node's data is 8, not equal to x so the ptrX will remain unchanged.

The current node data is 2, which is not equal to x so ptrX will remain unchanged.

The current node data is 0, equal to the value of x, so that that ptrX will be changed now.

The current node’s data is 0, equal to x, so the ptrX will now point to this node. 
Note that the ptrX will always point to the last occurrence of x in the traversed Linked List. For example, when we are at a node with data 2, the ptrX is at the 3rd Node, the last occurrence of x, up to that position. 
The above example requires a traversal of the linked list and deletion of nodes that contains the last occurrence of x.  

The current node’s data is 0, equal to x, so the ptrX will now point to this node.

Algorithm

  • Initialize a pointer variable named ptrX with NULL.
  • Start traversing through the linked list.
  • If the current node data is equal to value X (curr->data == X), move the ptrX to this current node.
  • Continue the above step till the end of the linked list.
  • When we reach the end, the special pointer points to the node that is the last occurring node with value X in the linked list.
  • Now we have to delete that node.

Java Implementation

The program to delete the last occurence of x in a Linked List is given below:

class Node{
    int data;
    Node next;
    
    public Node(int data)
    {
        this.data = data;
        this.next = null;
    }
}
class DeleteLastOccurence {
    // The main function to delete the last occurence of 
    // x in the Linked List
  static void deleteLastOccurence(Node head, int x)
    {
        Node temp = head;
        Node ptrX = null;
        
        while(temp != null)
        {
            if(temp.data == x)
            {
                ptrX = temp;
            }
            
            temp = temp.next;
        }
        
        // the ptrX is now pointing to the 
        // last occurence of x
        
        // If the last occurence is the last node
        if(ptrX != null && ptrX.next == null)
        {
            temp = head;
            while(temp.next != ptrX){
                temp = temp.next;
            }
            
            temp.next = null;
        }
        
        // If the last occurence is not the last node
        if(ptrX != null && ptrX.next != null){
            ptrX.data = ptrX.next.data;
            temp = ptrX.next;
            ptrX.next = ptrX.next.next;
            System.gc();
        }
        
    }
    
    static void displayLinkedList(Node head)
    {
        Node temp = head;
        if(head == null){
            System.out.print("null\n");
            return;
        }
    
        while(temp != null){
            System.out.print(temp.data + "->");
            temp = temp.next;
        }
        
        System.out.print("Null\n");
        
    }
    public static void main(String[] args) {
        Node head = new Node(0);
        head.next= new Node(3);
        head.next.next = new Node(0);
        head.next.next.next = new Node(8);
        head.next.next.next.next = new Node(2);
        head.next.next.next.next.next = new Node(0);
        head.next.next.next.next.next.next = new Node(0);
        head.next.next.next.next.next.next.next = new Node(0);
        displayLinkedList(head);
        int x = 0;
        deleteLastOccurence(head, x);
        System.out.println("\nDisplaying Linked list after deletion of last occurence of " + x);
        displayLinkedList(head);


        
    }
}
You can also try this code with Online Java Compiler
Run Code

Output

The output of the above program is 
0->3->0->8->2->0->0->0->Null 
Displaying Linked list after deletion of last occurence of 0 
0->3->0->8->2->0->0->Null

Complexity Analysis

Time complexity: In the above program, we traverse the linked list twice, once for finding the last occurrence of X and the second for the deletion process. That means the overall time complexity of the above program is O(N), where N is the number of nodes in the Linked list.

Space complexity: No extra space is required for the above program, so the space complexity is O(1), i.e., constant space complexity. 
In addition to the above implementation, Java also provides a method named removeLast() that can be used to remove the last occurrence of an element in a Linked List. 
Let's look at some of the Frequently asked questions related to deleting the last occurrence of nodes in a linked list.

Frequently Asked Questions

How do you remove the last element in a linked list in Java?

LinkedList.removeLast() method is used to remove the last element from the LinkedList. This method also returns the element after removing it.

How to remove an item from a Linked List?

You can remove an item from the beginning of the linked list, from the end of the linked list, or from any random position in the list.

How do you remove the last element in a linked list Python?

Deleting the last node of the Linked List involves checking the head for empty. If it is not empty, then check the head next for empty. If the head next is empty, release the head; otherwise, traverse to the second last node of the list. Then, link the next of the second last node to NULL and delete the last node.

 How to find the last node in a Linked list?

Take a temporary pointer, Node temp. Linearly iterate over the linked list using the temp pointer until the condition, temp.next != null is satisfied; the temp pointer points to the last node when the condition is satisfied.

 When some node is deleted from the linked list, what happens?

A move accompanies the delete operation. The next element of the previous item in the linked list now points to the element after the deleted one.

Conclusion

In this blog, we looked at an important interview question, delete the last occurrence of an element x in the linked list. We have discussed the approach, implementation, complexity analysis, and how to approach such questions in an interview. To truly excel in a programming interview, the only technique is PRACTICE. The more you practice, the better you become. You will find coding interview questionsguided paths, interview experiences, and many more expert-curated resources on Coding Ninjas Studio. So what are you waiting for? Go check out Coding Ninjas Studio and become a Ninja Programmer.

Happy Coding !!

 

Live masterclass