### Introduction

The linked list is the most crucial concept and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

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

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

- 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

### Code Implementation

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

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

So, In this blog, we have learned How to delete the last occurrence of an item from the linked list. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.