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; }
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