Using pointers, loop through the whole list and keep track of the node prior to the node containing the last occurrence key using a special pointer. After this just store the next of next of the special pointer, into to next of special pointer to remove the required node from the linked list.
C++
// C++ program to implement the // above approach#include <iostream>#include <bits/stdc++.h>using namespace std;// A linked list Nodestruct Node { int data; struct Node* next;};// Function to delete the last // occurrencevoid deleteLast(struct Node** head, int x){ struct Node** tmp1 = NULL; while (*head) { if ((*head)->data == x) { tmp1 = head; } head = &(*head)->next; } if (tmp1) { struct Node* tmp = *tmp1; *tmp1 = tmp->next; free(tmp); }}// Utility function to create a new // node with given key struct Node* newNode(int x){ Node* node = new Node ; node->data = x; node->next = NULL; return node;}// This function prints contents of // linked list starting from the given // Nodevoid display(struct Node* head){ struct Node* temp = head; if (head == NULL) { cout << "NULL"; return; } while (temp != NULL) { cout << temp->data << " --> "; temp = temp->next; } cout << "NULL";}// Driver codeint main(){ struct Node* head = newNode(1); 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); cout << "Created Linked list: "; display(head); // Pass the address of the head // pointer deleteLast(&head, 4); cout << "List after deletion of 4: "; display(head); return 0;}// This code is contributed by khushboogoyal499 |
Output:
Created Linked list: 1 --> 2 --> 3 --> 4 --> 5 --> 4 --> 4 --> NULL List after deletion of 4: 1 --> 2 --> 3 --> 4 --> 5 --> 4 --> NULL
Given a linked list and a key to be deleted. Delete last occurrence of key from linked. The list may have duplicates.
Examples:
Input: 1->2->3->5->2->10, key = 2 Output: 1->2->3->5->10
The idea is to traverse the linked list from beginning to end. While traversing, keep track of last occurrence key. After traversing the complete list, delete the last occurrence by copying data of next node and deleting the next node.
C++
// A C++ program to demonstrate deletion // of last Node in singly linked list#include <bits/stdc++.h>// A linked list Nodestruct Node { int key; struct Node* next;};void deleteLast(Node* head, int key){ // Initialize previous of Node // to be deleted Node* x = NULL; // Start from head and find the // Node to be deleted Node* temp = head; while (temp) { // If we found the key, // update xv if (temp->key == key) x = temp; temp = temp->next; } // Key occurs at-least once if (x != NULL) { // Copy key of next Node to x x->key = x->next->key; // Store and unlink next temp = x->next; x->next = x->next->next; // Free memory for next delete temp; }}/* Utility function to create a new node with given key */Node* newNode(int key){ Node* temp = new Node; temp->key = key; temp->next = NULL; return temp;}// This function prints contents of // linked list starting from the // given Nodevoid printList(struct Node* node){ while (node != NULL) { printf(" %d ", node->key); node = node->next; }}// Driver codeint main(){ // Start with the empty list struct Node* head = newNode(1); head->next = newNode(2); head->next->next = newNode(3); head->next->next->next = newNode(5); head->next->next->next->next = newNode(2); head->next->next->next->next->next = newNode(10); puts( "Created Linked List: "); printList(head); deleteLast(head, 2); puts( "Linked List after Deletion of 1: "); printList(head); return 0;} |
Output:
Created Linked List: 1 2 3 5 2 10 Linked List after Deletion of 1: 1 2 3 5 10
The above solution doesn’t work when the node to be deleted is the last node.
Following solution handles all cases.
C++
// A C++ program to demonstrate deletion // of last Node in singly linked list#include <bits/stdc++.h>using namespace std;// A linked list Nodestruct Node { int data; struct Node* next;};// Function to delete the last // occurrencevoid deleteLast(struct Node* head, int x){ struct Node *temp = head, *ptr = NULL; while (temp) { // 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; free(temp); }}/* Utility function to create a new node with given key */struct Node* newNode(int x){ Node* node = new Node ; node->data = x; node->next = NULL; return node;} // This function prints contents of // linked list starting from the given // Nodevoid display(struct Node* head){ struct Node* temp = head; if (head == NULL) { cout << "NULL"; return; } while (temp != NULL) { cout <<" --> "<< temp->data; temp = temp->next; } cout << "NULL";}// Driver codeint main(){ struct Node* head = newNode(1); 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); cout << "Created Linked list: "; display(head); deleteLast(head, 4); cout << "List after deletion of 4: "; display(head); return 0;}// This code is contributed by shivanisinghss2110 |
Output:
Created Linked List: 1 2 3 4 5 4 4 Linked List after Deletion of 1: 1 2 3 4 5 4
Please refer complete article on Delete last occurrence of an item from linked list for more details!
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
