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.
Java
// Java program to implement
// the above approach
import java.io.*;
// A linked list Node
class Node
{
int data;
Node next;
Node(int data)
{
this.data = data;
this.next = null;
}
}
class GFG{
// Function to delete the last
// occurrence
static Node deleteLast(Node head,
int x)
{
Node temp = head;
Node 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;
}
return head;
}
// This function prints contents of
// linked list starting from the given
// Node
static void display(Node head)
{
Node temp = head;
if (head == null)
{
System.out.print("NULL");
return;
}
while (temp != null)
{
System.out.print(temp.data +
" --> ");
temp = temp.next;
}
System.out.print("NULL");
}
// Driver code
public static void main(String[] args)
{
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next =
new Node(4);
head.next.next.next.next =
new Node(5);
head.next.next.next.next.next =
new Node(4);
head.next.next.next.next.next.next =
new Node(4);
System.out.print(
"Created Linked list: ");
display(head);
// Pass the address of the head
// pointer
head = deleteLast(head, 4);
System.out.print(
"List after deletion of 4: ");
display(head);
}
}
// This code is contributed by patel2127
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
Complejidad de tiempo: O(n) donde n es el número de Nodes en la lista enlazada dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
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.
Java
// A Java program to demonstrate deletion
// of last Node in singly linked list
class GFG{
// A linked list Node
static class Node
{
int key;
Node next;
};
static Node 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 != null)
{
// 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
}
return head;
}
// Utility function to create a
// new node with given key
static 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
static void printList( Node node)
{
while (node != null)
{
System.out.printf(" %d ",
node.key);
node = node.next;
}
}
// Driver code
public static void main(String args[])
{
// Start with the empty list
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);
System.out.printf("Created Linked List: ");
printList(head);
deleteLast(head, 2);
System.out.printf(
"Linked List after Deletion of 1: ");
printList(head);
}
}
// This code is contributed by Arnab Kundu
Producción:
Created Linked List: 1 2 3 5 2 10 Linked List after Deletion of 1: 1 2 3 5 10
Complejidad de tiempo: O(n) donde n es el número de Nodes en la lista enlazada dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
La solución anterior no funciona cuando el Node que se eliminará es el último Node.
La siguiente solución maneja todos los casos.
Java
// Java program to demonstrate deletion
// of last Node in singly linked list
class GFG{
// A linked list Node
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();
}
}
/* Utility function to create a
new node with given key */
static 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
static void display(Node head)
{
Node temp = head;
if (head == null)
{
System.out.print("null");
return;
}
while (temp != null)
{
System.out.printf("%d --> ",
temp.data);
temp = temp.next;
}
System.out.print("null");
}
// Driver code
public static void main(String[] args)
{
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);
System.out.print(
"Created Linked list: ");
display(head);
deleteLast(head, 4);
System.out.print(
"List after deletion of 4: ");
display(head);
}
}
// This code is contributed by PrinciRaj1992
Producción:
Created Linked List: 1 2 3 4 5 4 4 Linked List after Deletion of 1: 1 2 3 4 5 4
Complejidad de tiempo: O(n) donde n es el número de Nodes en la lista enlazada dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
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