Dada una lista enlazada individualmente y una posición, elimine un Node de lista enlazada en la posición dada.
Ejemplo:
Input: position = 1, Linked List = 8->2->3->1->7 Output: Linked List = 8->3->1->7 Input: position = 0, Linked List = 8->2->3->1->7 Output: Linked List = 2->3->1->7
Si el Node a eliminar es el raíz, simplemente elimínelo. Para eliminar un Node medio, debemos tener un puntero al Node anterior al Node a eliminar. Entonces, si las posiciones no son cero, ejecutamos un ciclo position-1 veces y obtenemos un puntero al Node anterior.
A continuación se muestra la implementación de la idea anterior.
C++
// A complete working C++ program to delete
// a node in a linked list at a given position
#include <iostream>
using namespace std;
// A linked list node
class Node
{
public:
int data;
Node *next;
};
// Given a reference (pointer to pointer) to
// the head of a list and an int inserts a
// new node on the front of the list.
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;
}
// Given a reference (pointer to pointer) to
// the head of a list and a position, deletes
// the node at the given position
void deleteNode(Node **head_ref, int position)
{
// If linked list is empty
if (*head_ref == NULL)
return;
// Store head node
Node* temp = *head_ref;
// If head needs to be removed
if (position == 0)
{
// Change head
*head_ref = temp->next;
// Free old head
free(temp);
return;
}
// Find previous node of the node to be deleted
for(int i = 0; temp != NULL && i < position - 1; i++)
temp = temp->next;
// If position is more than number of nodes
if (temp == NULL || temp->next == NULL)
return;
// Node temp->next is the node to be deleted
// Store pointer to the next of node to be deleted
Node *next = temp->next->next;
// Unlink the node from linked list
free(temp->next); // Free memory
// Unlink the deleted node from list
temp->next = next;
}
// This function prints contents of linked
// list starting from the given node
void printList( Node *node)
{
while (node != NULL)
{
cout << node->data << " ";
node = node->next;
}
}
// Driver code
int main()
{
// Start with the empty list
Node* head = NULL;
push(&head, 7);
push(&head, 1);
push(&head, 3);
push(&head, 2);
push(&head, 8);
cout << "Created Linked List: ";
printList(head);
deleteNode(&head, 4);
cout << "
Linked List after Deletion at position 4: ";
printList(head);
return 0;
}
// This code is contributed by premsai2030
Producción:
Created Linked List: 8 2 3 1 7 Linked List after Deletion at position 4: 8 2 3 1
Complejidad de tiempo: O(n), donde n representa la longitud de 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 un Node de lista vinculada en una posición determinada 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