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.
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("");
// Lets 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
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