Dada una lista enlazada individualmente, escriba una función para eliminar un Node determinado. Su función debe seguir las siguientes restricciones:
1) 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.
2) No debería devolver un puntero al Node principal.
3) 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 al encabezado 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 << "\nGiven 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<<"\nDeleting node "<< head->next->next->data<<" "; deleteNode(head, head->next->next); cout<<"\nModified Linked List: "; printList(head); /* Let us delete the first node */ cout<<"\nDeleting first node "; deleteNode(head, head); cout<<"\nModified Linked List: "; printList(head); return 0; } // This code is contributed by rathbhupendra
C
#include <stdio.h> #include <stdlib.h> /* structure of a linked list node */ struct Node { int data; struct Node *next; }; void deleteNode(struct Node *head, struct Node *n) { // When node to be deleted is head node if(head == n) { if(head->next == NULL) { printf("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 struct 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) { printf("\n 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(struct Node **head_ref, int new_data) { struct Node *new_node = (struct Node *)malloc(sizeof(struct Node)); new_node->data = new_data; new_node->next = *head_ref; *head_ref = new_node; } /* Utility function to print a linked list */ void printList(struct Node *head) { while(head!=NULL) { printf("%d ",head->data); head=head->next; } printf("\n"); } /* Driver program to test above functions */ int main() { struct 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); printf("Given Linked List: "); printList(head); /* Let us delete the node with value 10 */ printf("\nDeleting node %d: ", head->next->next->data); deleteNode(head, head->next->next); printf("\nModified Linked List: "); printList(head); /* Let us delete the first node */ printf("\nDeleting first node "); deleteNode(head, head); printf("\nModified Linked List: "); printList(head); getchar(); return 0; }
Python 3
# Node class class Node: def __init__(self, data): self.data = data self.next = None # LinkedList class class LinkedList: def __init__(self): self.head = None def deleteNode(self, data): temp = self.head prev = self.head if temp.data == data: if temp.next is None: print("Can't delete the node as it has only one node") else: temp.data = temp.next.data temp.next = temp.next.next return while temp.next is not None and temp.data != data: prev = temp temp = temp.next if temp.next is None and temp.data !=data: print("Can't delete the node as it doesn't exist") # If node is last node of the linked list elif temp.next is None and temp.data == data: prev.next = None else: prev.next = temp.next # To push a new element in the Linked List def push(self, new_data): new_node = Node(new_data) new_node.next = self.head self.head = new_node # To print all the elements of the Linked List def PrintList(self): temp = self.head while(temp): print(temp.data, end = " ") temp = temp.next # Driver Code llist = LinkedList() llist.push(3) llist.push(2) llist.push(6) llist.push(5) llist.push(11) llist.push(10) llist.push(15) llist.push(12) print("Given Linked List: ", end = ' ') llist.PrintList() print("\n\nDeleting node 10:") llist.deleteNode(10) print("Modified Linked List: ", end = ' ') llist.PrintList() print("\n\nDeleting first node") llist.deleteNode(12) print("Modified Linked List: ", end = ' ') llist.PrintList() # This code is contributed by Akarsh Somani
Java
// Java program to delete a given node // in linked list under given constraints class LinkedList { static Node head; static class Node { int data; Node next; Node(int d) { data = d; next = null; } } void deleteNode(Node node, Node n) { // When node to be deleted is head node if (node == n) { if (node.next == null) { System.out.println("There is only one node. The list " + "can't be made empty "); return; } /* Copy the data of next node to head */ node.data = node.next.data; // store address of next node n = node.next; // Remove the link of next node node.next = node.next.next; // free memory System.gc(); return; } // When not first node, follow the normal deletion process // find the previous node Node prev = node; while (prev.next != null && prev.next != n) { prev = prev.next; } // Check if node really exists in Linked List if (prev.next == null) { System.out.println("Given node is not present in Linked List"); return; } // Remove node from Linked List prev.next = prev.next.next; // Free memory System.gc(); return; } /* Utility function to print a linked list */ void printList(Node head) { while (head != null) { System.out.print(head.data + " "); head = head.next; } System.out.println(""); } public static void main(String[] args) { LinkedList list = new LinkedList(); list.head = new Node(12); list.head.next = new Node(15); list.head.next.next = new Node(10); list.head.next.next.next = new Node(11); list.head.next.next.next.next = new Node(5); list.head.next.next.next.next.next = new Node(6); list.head.next.next.next.next.next.next = new Node(2); list.head.next.next.next.next.next.next.next = new Node(3); System.out.println("Given Linked List :"); list.printList(head); System.out.println(""); // Let us delete the node with value 10 System.out.println("Deleting node :" + head.next.next.data); list.deleteNode(head, head.next.next); System.out.println("Modified Linked list :"); list.printList(head); System.out.println(""); // Let us delete the first node System.out.println("Deleting first Node"); list.deleteNode(head, head); System.out.println("Modified Linked List"); list.printList(head); } } // this code has been contributed by Mayank Jaiswal
C#
// C# program to delete a given // node in linked list under // given constraints using System; public class LinkedList { Node head; class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } } void deleteNode(Node node, Node n) { // When node to be deleted is head node if (node == n) { if (node.next == null) { Console.WriteLine("There is only one node. The list " + "can't be made empty "); return; } /* Copy the data of next node to head */ node.data = node.next.data; // store address of next node n = node.next; // Remove the link of next node node.next = node.next.next; // free memory GC.Collect(); return; } // When not first node, follow // the normal deletion process // find the previous node Node prev = node; while (prev.next != null && prev.next != n) { prev = prev.next; } // Check if node really exists in Linked List if (prev.next == null) { Console.WriteLine("Given node is not" + "present in Linked List"); return; } // Remove node from Linked List prev.next = prev.next.next; // Free memory GC.Collect(); return; } /* Utility function to print a linked list */ void printList(Node head) { while (head != null) { Console.Write(head.data + " "); head = head.next; } Console.WriteLine(""); } // Driver code public static void Main(String[] args) { LinkedList list = new LinkedList(); list.head = new Node(12); list.head.next = new Node(15); list.head.next.next = new Node(10); list.head.next.next.next = new Node(11); list.head.next.next.next.next = new Node(5); list.head.next.next.next.next.next = new Node(6); list.head.next.next.next.next.next.next = new Node(2); list.head.next.next.next.next.next.next.next = new Node(3); Console.WriteLine("Given Linked List :"); list.printList(list.head); Console.WriteLine(""); // Let us delete the node with value 10 Console.WriteLine("Deleting node :" + list.head.next.next.data); list.deleteNode(list.head, list.head.next.next); Console.WriteLine("Modified Linked list :"); list.printList(list.head); Console.WriteLine(""); // Let us delete the first node Console.WriteLine("Deleting first Node"); list.deleteNode(list.head, list.head); Console.WriteLine("Modified Linked List"); list.printList(list.head); } } // This code is contributed by Rajput-Ji
Javascript
<script> // javascript program to delete a given node // in linked list under given constraints var head; class Node { constructor(val) { this.data = val; this.next = null; } } function deleteNode( node, n) { // When node to be deleted is head node if (node == n) { if (node.next == null) { document.write("There is only one node. The list " + "can't be made empty "); return; } /* Copy the data of next node to head */ node.data = node.next.data; // store address of next node n = node.next; // Remove the link of next node node.next = node.next.next; // free memory return; } // When not first node, follow the normal deletion process // find the previous node prev = node; while (prev.next != null && prev.next != n) { prev = prev.next; } // Check if node really exists in Linked List if (prev.next == null) { document.write("Given node is not present in Linked List"); return; } // Remove node from Linked List prev.next = prev.next.next; return; } /* Utility function to print a linked list */ function printList( head) { while (head != null) { document.write(head.data + " "); head = head.next; } document.write(""); } head = new Node(12); head.next = new Node(15); head.next.next = new Node(10); head.next.next.next = new Node(11); head.next.next.next.next = new Node(5); head.next.next.next.next.next = new Node(6); head.next.next.next.next.next.next = new Node(2); head.next.next.next.next.next.next.next = new Node(3); document.write("Given Linked List :"); printList(head); document.write(""); // Let us delete the node with value 10 document.write("<br/>Deleting node :" + head.next.next.data); deleteNode(head, head.next.next); document.write("<br/>Modified Linked list :"); printList(head); document.write("<br/>"); // Let us delete the first node document.write("Deleting first Node<br/>"); deleteNode(head, head); document.write("Modified Linked List"); printList(head); // This code is contributed by todaysgaurav </script>
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)
Como estamos recorriendo la lista solo una vez.
Espacio Auxiliar: O(1)
Como espacio adicional constante se utiliza.
Escriba comentarios si encuentra que los códigos/algoritmos anteriores son incorrectos o encuentra otras formas de resolver el mismo problema.
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