Dada una lista enlazada individualmente, escriba una función para eliminar un Node determinado. Su función debe seguir las siguientes restricciones:
- Debe aceptar un puntero al Node de inicio como primer parámetro y el Node a eliminar como segundo parámetro, es decir, un puntero al Node principal no es global.
- No debe devolver un puntero al Node principal.
- No debe aceptar puntero a puntero al Node principal.
Puede suponer que la lista enlazada nunca se vacía.
Deje que el nombre de la función sea deleteNode(). En una implementación sencilla, la función necesita modificar el puntero principal cuando el Node que se eliminará es el primer Node. Como se discutió en la publicación anterior , cuando una función modifica el puntero principal, la función debe usar uno de los enfoques dados , no podemos usar ninguno de esos enfoques aquí.
Solución:
Manejamos explícitamente el caso cuando el Node que se va a eliminar es el primer Node, copiamos los datos del siguiente Node a la cabecera y eliminamos el siguiente Node. Los casos en los que un Node eliminado no es el Node principal se pueden manejar normalmente encontrando el Node anterior y cambiando el siguiente del Node anterior. Las siguientes son las implementaciones.
C++
// C++ program to delete a given node
// in linked list under given constraints
#include <bits/stdc++.h>
using namespace std;
// Structure of a linked list
// node
class Node
{
public:
int data;
Node *next;
};
void deleteNode(Node *head,
Node *n)
{
// When node to be deleted is
// head node
if(head == n)
{
if(head->next == NULL)
{
cout << "There is only one node." <<
" The list can't be made empty ";
return;
}
// Copy the data of next node
// to head
head->data = head->next->data;
// Store address of next node
n = head->next;
// Remove the link of next node
head->next = head->next->next;
// Free memory
free(n);
return;
}
// When not first node, follow
// the normal deletion process
// Find the previous node
Node *prev = head;
while(prev->next != NULL &&
prev->next != n)
prev = prev->next;
// Check if node really exists in
// Linked List
if(prev->next == NULL)
{
cout <<
"Given node is not present in Linked List";
return;
}
// Remove node from Linked List
prev->next = prev->next->next;
// Free memory
free(n);
return;
}
/* Utility function to insert a
node at the beginning */
void push(Node **head_ref,
int new_data)
{
Node *new_node = new Node();
new_node->data = new_data;
new_node->next = *head_ref;
*head_ref = new_node;
}
/* Utility function to print a
linked list */
void printList(Node *head)
{
while(head != NULL)
{
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
// Driver code
int main()
{
Node *head = NULL;
/* Create following linked list
12->15->10->11->5->6->2->3 */
push(&head,3);
push(&head,2);
push(&head,6);
push(&head,5);
push(&head,11);
push(&head,10);
push(&head,15);
push(&head,12);
cout << "Given Linked List: ";
printList(head);
/* Let us delete the node with
value 10 */
cout << "Deleting node " <<
head->next->next->data << " ";
deleteNode(head, head->next->next);
cout << "Modified Linked List: ";
printList(head);
// Let us delete the first node
cout << "Deleting first node ";
deleteNode(head, head);
cout << "Modified Linked List: ";
printList(head);
return 0;
}
// This code is contributed by rathbhupendra
Producción:
Given Linked List: 12 15 10 11 5 6 2 3 Deleting node 10: Modified Linked List: 12 15 11 5 6 2 3 Deleting first node Modified Linked List: 15 11 5 6 2 3
Complejidad de tiempo: O(n), donde n representa el tamaño de la array dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
¡ Consulte el artículo completo sobre Eliminar un Node dado en la Lista vinculada bajo las restricciones dadas 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