Se le proporciona una lista enlazada individualmente y un puntero que apunta al Node que debe eliminarse. No se proporciona ninguna información sobre el puntero principal o cualquier otro Node. Debe escribir una función para eliminar ese Node de la lista vinculada . Su función tomará solo un argumento, es decir, un puntero al Node que se eliminará.
Nota: No se le da ninguna referencia principal a usted. Se garantiza que el Node a eliminar no sea el último Node.
Una lista enlazada se construye como:
La definición de cada Node es la siguiente:
struct Node {
int data;
estructura Node* siguiente;
};
Ejemplos:
Considere a continuación LL para ejemplos dados:
Entrada: C (un puntero a C)
Salida: A–>B–>D–>E–>F
Entrada: A (un puntero a A)
Salida: B–>D–>E–>F
Acercarse:
¿Por qué el método de eliminación convencional fallaría aquí?
Sería un simple problema de eliminación de la lista de enlaces individuales si se proporcionara el puntero principal porque para la eliminación debe conocer el Node anterior y puede llegar fácilmente a él atravesando desde el puntero principal. La eliminación convencional es imposible sin el conocimiento del Node anterior de un Node que debe eliminarse.
¿Cómo eliminar el Node cuando no tienes el puntero principal?
El truco aquí es que podemos copiar los datos del siguiente Node al campo de datos del Node actual para eliminarlos. Entonces podemos dar un paso adelante. Ahora nuestro siguiente se ha convertido en el Node actual y el actual se ha convertido en el Node anterior. Ahora podemos eliminar fácilmente el Node actual mediante métodos de eliminación convencionales.
Ilustración:
Por ejemplo, supongamos que necesitamos eliminar B y se proporciona un puntero a B.
Si tuviéramos un puntero a A, podríamos haber eliminado B fácilmente.
Pero aquí copiaremos el campo de datos de C al campo de datos de B. Luego seguiremos adelante.Ahora estamos en C y tenemos un puntero a B, es decir, el puntero anterior. Así que eliminaremos C.
Así es como se eliminará el Node B.
La imagen de abajo es una ejecución en seco del enfoque anterior:
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ program to delete a node
#include <bits/stdc++.h>
using namespace std;
/* Link list node */
struct Node {
int data;
struct Node* next;
};
// Function to delete the node without head
void deleteNodeWithoutHead(struct Node* pos)
{
if (pos == NULL) // If linked list is empty
return;
else {
if (pos->next == NULL) {
printf("This is last node, require head, can't "
"be freed\n");
return;
}
struct Node* temp = pos->next;
// Copy data of the next node to current node
pos->data = pos->next->data;
// Perform conventional deletion
pos->next = pos->next->next;
free(temp);
}
}
// Function to print the linked list
void print(Node* head)
{
Node* temp = head;
while (temp) {
cout << temp->data << " -> ";
temp = temp->next;
}
cout << "NULL";
}
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node = new Node();
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
// Driver Code
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
// create linked 35->15->4->20
push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 35);
cout << "Initial Linked List: \n";
print(head);
cout << endl << endl;
// Delete 15 without sending head
Node* del = head->next;
deleteNodeWithoutHead(del);
// Print the final linked list
cout << "Final Linked List after deletion of 15:\n";
print(head);
return 0;
// This code has been contributed by Striver
}
Initial Linked List: 35 -> 15 -> 4 -> 20 -> NULL Final Linked List after deletion of 15: 35 -> 4 -> 20 -> NULL
Complejidad de tiempo : O (1) desde que se realizan operaciones constantes y se modifica solo un puntero para eliminar el Node
Espacio Auxiliar: O(1)
Este artículo es una contribución de Jeet Jain . Consulte Dado solo un puntero a un Node que se eliminará en una lista vinculada individualmente, ¿cómo se elimina para obtener más detalles y una implementación completa?