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