Elimine múltiples apariciones de clave en la lista Vinculada usando doble puntero

Dada una lista enlazada individualmente, elimine todas las apariciones de una clave dada en ella. Por ejemplo, considere la siguiente lista. 

Input: 2 -> 2 -> 4 -> 3 -> 2
       Key to delete = 2
Output:  4 -> 3 

Esta es principalmente una alternativa de esta publicación que elimina múltiples apariciones de una clave determinada utilizando bucles de condición separados para la cabeza y los Nodes restantes. Aquí usamos un enfoque de doble puntero para usar un solo bucle independientemente de la posición del elemento (cabeza, cola o entre). Linus Torvalds explicó el método original para eliminar un Node de una lista enlazada sin una verificación adicional de la cabeza en su charla TED «25 aniversario de Linux». Este artículo usa esa lógica para eliminar múltiples recurrencias de la clave sin una verificación adicional para el encabezado. Explicación: 1. Almacene la dirección del encabezado en un puntero doble hasta que encontremos un Node que no sea «clave». Esto se ocupa del primer ciclo while para manejar el caso especial de la cabeza. 2. Si un Node no es un Node «clave», almacene la dirección del Node->siguiente en la página 3. Si encontramos un Node «clave» más adelante, cambie pp (en última instancia, Node->siguiente) para que apunte al Node actual ->siguiente. A continuación se muestra la implementación de C++ para el mismo. 

CPP

// CPP program to delete multiple
// occurrences of a key using single
// loop.
#include <iostream>
using namespace std;
 
// A linked list node
struct Node {
 int data;
 struct Node* next;
};
 
struct Node* head = NULL;
 
void printList(struct Node* node)
{
 while (node != NULL) {
  printf(" %d ", node->data);
  node = node->next;
 }
}
 
void push(int new_data)
{
 struct Node* new_node = new Node;
 new_node->data = new_data;
 new_node->next = (head);
 (head) = new_node;
}
 
void deleteEntry(int key)
{
 // Start from head
 struct Node** pp = &head;
 while (*pp) {
 
  struct Node* entry = *pp;
 
  // If key found, then put
  // next at the address of pp
  // delete entry.
  if (entry->data == key) {
   *pp = entry->next;
   delete (entry);
  }
 
  // Else move to next
  else
   pp = &(entry->next);
 }
}
 
int main()
{
 push(2);
 push(2);
 push(4);
 push(3);
 push(2);
 
 int key = 2; // key to delete
 
 puts("Created Linked List: ");
 printList(head);
 printf("\n");
 deleteEntry(key);
 printf("\nLinked List after Deletion of 2: \n");
 printList(head);
 return 0;
}
Producción:

Created Linked List: 
 2  3  4  2  2 

Linked List after Deletion of 2: 
 3  4

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1), ya que no se requiere espacio extra

Publicación traducida automáticamente

Artículo escrito por NayanGadre y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *