Usando punteros, recorra toda la lista y realice un seguimiento del Node anterior al Node que contiene la última clave de ocurrencia usando un puntero especial. Después de esto, simplemente almacene el siguiente del siguiente del puntero especial, en el siguiente del puntero especial para eliminar el Node requerido de la lista vinculada.
C++
// C++ program to implement the
// above approach
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// A linked list Node
struct Node
{
int data;
struct Node* next;
};
// Function to delete the last
// occurrence
void 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
// Node
void 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 code
int 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
Producción:
Created Linked list: 1 --> 2 --> 3 --> 4 --> 5 --> 4 --> 4 --> NULL List after deletion of 4: 1 --> 2 --> 3 --> 4 --> 5 --> 4 --> NULL
Dada una lista enlazada y una clave para ser eliminada. Elimine la última aparición de la clave del enlace. La lista puede tener duplicados.
Ejemplos :
Input: 1->2->3->5->2->10, key = 2 Output: 1->2->3->5->10
La idea es recorrer la lista enlazada de principio a fin. Mientras atraviesa, realice un seguimiento de la última clave de aparición. Después de recorrer la lista completa, elimine la última aparición copiando los datos del siguiente Node y eliminando el siguiente Node.
C++
// A C++ program to demonstrate deletion
// of last Node in singly linked list
#include <bits/stdc++.h>
// A linked list Node
struct 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 Node
void printList(struct Node* node)
{
while (node != NULL)
{
printf(" %d ",
node->key);
node = node->next;
}
}
// Driver code
int 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;
}
Producción:
Created Linked List: 1 2 3 5 2 10 Linked List after Deletion of 1: 1 2 3 5 10
La solución anterior no funciona cuando el Node que se eliminará es el último Node.
La siguiente solución maneja todos los casos.
C++
// A C++ program to demonstrate deletion
// of last Node in singly linked list
#include <bits/stdc++.h>
using namespace std;
// A linked list Node
struct Node
{
int data;
struct Node* next;
};
// Function to delete the last
// occurrence
void 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
// Node
void 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 code
int 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
Producción:
Created Linked List: 1 2 3 4 5 4 4 Linked List after Deletion of 1: 1 2 3 4 5 4
Consulte el artículo completo sobre Eliminar la última aparición de un elemento de la lista vinculada para obtener más detalles.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA