Delete the last occurrence of an item from the linked list

From a coding interview’s perspective Linked list plays an important role whether it be an online test or a face-to-face interview therefore there is a question “Delete the last occurrence of an item from the linked list”. Please think about the problem independently and try to figure out the approach on how to delete the last occurrence of an item from the linked list.

Problem Statement

In this problem, we are given a linked list and asked to delete the last occurrence of an item X from the linked list.

Problem Statement Understanding

We have been given a linked list and a value X. We have to delete the last occurrence of the item X from the linked list.

Let’s understand this problem with an examples.

If the linked list given to us is: head→1→2→7→5→2→10 and X = 2.

  • According to the problem statement, first, we will have to find the last occurrence of X = 2 in the linked list, i.e., last node towards the end of the linked list which had node -> data == X, and then we will have to delete it from the linked list.
  • Our linked list after deleting the last occurrence of X = 2 will be: head→1→2→7→5→10.

Suppose if the linked list is: head→1→3→5→7→7→7 and X=7.

  • Then, in this case, after deleting the last occurrence of X = 7 from the linked list our linked list will be head→1→3→5→7→7.
Some more examples:

Sample Input 1: head→1→1→3→5→1→9, X = 1.
Sample Output 1: head→1→1→3→5→9

Sample Input 2: head→1→3→3→5→3→9→3→5→3→3, X = 3.
Sample Output 2: head→1→3→3→5→3→9→3→5→3

Now I think from the above example, the problem statement is clear. So let’s see how we will approach it.

Before moving to the approach section, try to think about how you can approach this problem.

  • If stuck, no problem, we will thoroughly see how we can approach the problem in the next section.

Let’s move to the approach section.

Approach to delete the last occurrence of an item from the linked list

Our approach will be simple:

  • The idea is to initialize a special pointer variable and start traversing through the linked list.
  • During the traversal, Whenever the current node’s data is matching with value X, i.e., node -> data == X, move the special pointer to the current node.
  • When we reach the end of the linked list, the special pointer will be pointing to the last occurrence of X in the linked list.
  • Now we will have to delete the node to which special pointer is pointing.
  • Finally, after deleting the node to which the special pointer points, our objective will be satisfied.

Let’s move to the algorithm section.

Algorithm to delete the last occurrence of an item from the linked list

  • Initialize a pointer variable named special with NULL.
  • Start traversing through the linked list.
  • If the current node data is equal to value X (curr->data == X), move the special pointer to this current node.
  • Continue the above step till the end of the linked list.
  • When we reach the end, At that point of time, 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.
  • For deletion of that node, run a loop and reach the node prior to the node containing the last occurrence, i.e., the node to which special pointer is pointing.
  • Now link the node before the special pointer and node after the special pointer together, and delete the special node.
  • Finally, after deleting the node, our objective of deleting the last occurrence of X from the linked list will be satisfied.

Dry Run on delete the last occurrence of an item from the linked list

Implementation of delete the last occurrence of an item from the linked list

#include <stdio.h>
#include <stdlib.h>
 
// A linked list Node
struct Node {
    int data;
    struct Node* next;
};
 
void deleteLast(struct Node* head, int x)
{
    struct Node *temp = head, *ptr = NULL;
    while (temp) {
 
        if (temp->data == x)
            ptr = temp;       
        temp = temp->next;
    }
 
    // If the last occurrence is the last node
    if (ptr != NULL && ptr->next == NULL) {
        temp = head;
        while (temp->next != ptr)
            temp = temp->next;      
        temp->next = NULL;
    }
 
    // If it is not the last node
    if (ptr != NULL && ptr->next != NULL) {
        ptr->data = ptr->next->data;
        temp = ptr->next;
        ptr->next = ptr->next->next;
        free(temp);
    }
}
 
struct Node* newNode(int x)
{
    struct Node* node = malloc(sizeof(struct Node*));
    node->data = x;
    node->next = NULL;
    return node;
}
 
void display(struct Node* head)
{
    struct Node* temp = head;
    if (head == NULL) {
        printf("NULL\n");
        return;
    }
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main()
{
    struct Node* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(7);
    head->next->next->next = newNode(5);
    head->next->next->next->next = newNode(2);
    head->next->next->next->next->next = newNode(10);
    printf("Input Linked list: ");
    display(head);
    deleteLast(head, 2);
    printf("List after deletion of 4: ");
    display(head);
    return 0;
}


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

// A linked list Node
class Node {
    public:
    int data;
    Node* next;
};

void deleteLast(Node* head, int X){
    // Initialize special pointer with NULL
    Node* special = NULL;

    // Start from head and find the last Occurrence
    // of node with value X
    Node* temp = head;
    while (temp) {
        // If we found the key, update special
        if (temp->data == X)
            special = temp;

        temp = temp->next;
    }

    // key occurs at-least once
    if (special != NULL) {
        Node* removeNode = head;
        while(removeNode->next != special){
            removeNode = removeNode->next;
        }
        removeNode->next = special->next;
        special->next = NULL;
        delete special;
    }
    
}

// function to create a new node with given data
Node* newNode(int data){
    Node* temp = new Node;
    temp->data = data;
    temp->next = NULL;
    return temp;
}

// function to print the linked list
void printList(Node* node){
    while (node != NULL) {
        cout<<node->data<<" ";
        node = node->next;
    }
}

int main(){
    Node* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(7);
    head->next->next->next = newNode(5);
    head->next->next->next->next = newNode(2);
    head->next->next->next->next->next = newNode(10);

    cout<<"Input Linked List: ";
    printList(head);cout<<endl;
    deleteLast(head, 2);
    cout<<"Output Linked List: ";
    printList(head);
    return 0;
}
class DeleteOccurances
{


static class Node
{
    int data;
    Node next;
};

// Function to delete the last occurrence
static void deleteLast(Node head, int x)
{
    Node temp = head, ptr = null;
    while (temp!=null)
    {

        // If found key, update
        if (temp.data == x)
            ptr = temp;    
        temp = temp.next;
    }

    // If the last occurrence is the last node
    if (ptr != null && ptr.next == null)
    {
        temp = head;
        while (temp.next != ptr)
            temp = temp.next;
        temp.next = null;
    }

    // If it is not the last node
    if (ptr != null && ptr.next != null)
    {
        ptr.data = ptr.next.data;
        temp = ptr.next;
        ptr.next = ptr.next.next;
        System.gc();
    }
}
static Node newNode(int x)
{
    Node node = new Node();
    node.data = x;
    node.next = null;
    return node;
}
static void display(Node head)
{
    Node temp = head;
    if (head == null)
    {
        System.out.print("null\n");
        return;
    }
    while (temp != null)
    {
        System.out.printf("%d --> ", temp.data);
        temp = temp.next;
    }
    System.out.print("null\n");
}

/* Driver code*/
public static void main(String[] args)
{
    Node head = newNode(11);
    head.next = newNode(2);
    head.next.next = newNode(3);
    head.next.next.next = newNode(4);
    head.next.next.next.next = newNode(5);
    head.next.next.next.next.next = newNode(4);
    head.next.next.next.next.next.next = newNode(4);
    System.out.print("Created Linked list: ");
    display(head);
    deleteLast(head, 4);
    System.out.print("List after deletion of 4: ");
    display(head);
}
}
class Node:
    def __init__(self, new_data):
        
        self.data = new_data
        self.next = None

def deleteLast(head, x):

    temp = head
    ptr = None
    
    while (temp != None):

        if (temp.data == x):
            ptr = temp    
        temp = temp.next
    
    if (ptr != None and ptr.next == None):
        temp = head
        while (temp.next != ptr):
            temp = temp.next
            
        temp.next = None
    
    if (ptr != None and ptr.next != None):
        ptr.data = ptr.next.data
        temp = ptr.next
        ptr.next = ptr.next.next
        
    return head
    
def newNode(x):

    node = Node(0)
    node.data = x
    node.next = None
    return node

def display(head):

    temp = head
    if (head == None):
        print("NULL\n")
        return
    
    while (temp != None):
        print( temp.data, end = " ")
        temp = temp.next
    
    print("NULL")

head = newNode(1)
head.next = newNode(2)
head.next.next = newNode(7)
head.next.next.next = newNode(5)
head.next.next.next.next = newNode(2)
head.next.next.next.next.next = newNode(10)

print("Created Linked list: ", end = '')
display(head)

# Pass the address of the head pointer
head = deleteLast(head, 2)
print("List after deletion of 4: ", end = '')

display(head)

Output

Input Linked List: 1 2 7 5 2 10

Output Linked List: 1 2 7 5 10

Time Complexity: O(N), Since we traversed through the list two times, One traversal for finding the last occurred node of value X in the linked list and another traversal for the deletion process.

In this blog, we have explained the problem of “How to delete the last occurrence of an item from the linked list” very effectively and we will hope this blog will help you to enhance your knowledge regarding the linked list concepts. And if you want to solve more problems on Linked List, which is curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Related Articles
Doubly circular linked list in data structure Application of doubly linked list
Applications of linked list Singly linked list vs doubly linked list
Advantages and disadvantages of linked list Doubly linked list all operations in C
Binary search in linked list Bubble sort linked list
Deletion in doubly linked list Delete the middle node of a linked list
Polynomial addition using linked list Find max value and min value in linked list
Insert a node at a specific position in a linked list Swap nodes in linked list
Add two numbers represented by linked lists Find starting point of loop in linked list
Merge sort linked list Delete a node from linked list at a given position
Remove duplicates from unsorted linked list Reverse a linked list in Python

FAQs

  1. How do you remove the last element in a linked list in java?
  2. In Java, there is a method called LinkedList.removeLast() which is used to remove the last element from the linked list.

  3. How to find the last node in a linked list?
  4. You can find the last node in such a way:

    • Take a temp variable.
    • Iterate the linked list, until the condition fails.
    • temp.next != null
    • The temp pointer points to the last node of the linked list.
  5. How do you delete an item from a linked list?
  6. To delete a node from a linked list:

    • Find the previous node of the node which we have to delete.
    • Change the next pointer of the previous node.
    • Free the memory for the node which will be deleted.

Leave a Reply

Your email address will not be published. Required fields are marked *