Eliminación de cualquier nodo de una sola lista vinculada cuando solo se da un puntero a ese nodo

Question

Esta es una pregunta que se me hizo en una entrevista.

"Hay una sola lista vinculada en la memoria. Debe eliminar un nodo. Debe escribir una función para eliminar ese nodo, que toma solo la dirección del nodo que se eliminará como entrada y nada más (incluyendo la cabeza) "

Di la respuesta similar a la respuesta en la publicación a continuación - Copiando el contenido del siguiente nodo en el nodo a eliminar y eliminando el siguiente.

Deleting a middle node from a single linked list when pointer to the previous node is not available

Pero el entrevistador me preguntó de nuevo, lo que si paso la dirección del último nodo. Le dije, ya que el siguiente será un NULL, copie ese NULL en el campo de datos junto con la dirección al siguiente nodo que también sea NULL. Luego me dijo que habría un problema de punteros colgantes ... que no entendí un poco. ¿Puede alguien arrojar luz sobre este problema? ¿Hay una solución genérica para esto?

Actualización (Dos días después): Un poco más. Teniendo en cuenta que no hay ningún nodo especial al final de la lista. Y el último nodo apunta a NULL y si ese nodo se da como entrada, cómo hacer que el anterior nodo sea NULL. ¿O es imposible?

En pocas palabras: si un nodo se da como entrada para una función, cómo hacer que el puntero que hace referencia a ella, seleccione NULL

Answer 1

colgando Puntero:

(http://en.wikipedia.org/wiki/Dangling_reference)

referencia colgante y punteros salvajes en la programación de computadoras son punteros que no apuntan a una válida objeto del tipo apropiado. Estos son casos especiales de violaciones a la seguridad de la memoria. surgen

referencia colgante cuando se suprime o se cancela la asignación de un objeto, sin modificar el valor del puntero, por lo que el cursor quieto apunta a la ubicación de memoria de la memoria desasignado. Como el sistema puede reasignar la memoria liberada anteriormente a otro proceso, si el programa original luego desreferencia el puntero colgante (ahora), comportamiento impredecible puede resultar, ya que la memoria ahora puede contener datos completamente diferentes.

En su respuesta, para eliminar el nodo dado que elimina realmente la próxima nodo, que podría ser referenciado por un puntero. Así es como surgen los problemas del puntero colgante.

(1) No hay referencias externas a la lista, como puede aclarar en una nota. (2) Puede surgir un problema con el puntero colgante, como dijo el entrevistador.

Ambos (1) y (2) no pueden ser correctos al mismo tiempo. Lo que significa que hay un malentendido en alguna parte.

acerca de cómo eliminar el último nodo:

Pero el entrevistador me preguntó de nuevo, lo que si paso la dirección del último nodo . Le dije, ya que el siguiente será un NULL, copie ese NULL en el campo de datos junto con la dirección al siguiente nodo que es también NULL.

Creo que estás confundiendo estas dos cosas: (1) Un puntero p que apunta a NULL, (2) Un nodo de lista vinculada que tiene NULL en su campo de datos.

Supongamos que la estructura de datos es a -> b -> c -> d. Escribir NULL en el campo de datos de D's no hará que c tenga un puntero NULL mágicamente en su campo next.

Puede eliminar el último nodo si la lista vinculada siempre tiene un último nodo especial que nunca se eliminará. Por ejemplo, a -> b -> c -> d -> LAST donde LAST tiene un valor especial en su campo de datos que denota que es realmente el último elemento. Ahora para eliminar d, puede eliminar LAST y escribir el valor especial en el campo de datos de d's.

Quizás esto sea exactamente lo que intentó decir durante la entrevista, en cuyo caso debe haber habido alguna falta de comunicación entre usted y el entrevistador.

Answer 2

Si hay otros elementos que apuntan a la siguiente nodo que se van a copiar al nodo actual y luego eliminado, entonces esta operación introducirá un error. Entonces, en su respuesta debería haber enfatizado que su solución solo funciona si no hay referencias externas a la lista.

Su solución funciona con el último nodo solo si la estructura de datos se aumenta con un elemento específico de "último nodo". (Si está utilizando Smalltalk, puede escribir self become: nil Ningún otro idioma tiene algo similar)

No, no hay una solución genérica si hay referencias externas a la lista. Creo que el entrevistador quiso saber si usted es realmente conocedor del tema o simplemente estaba repitiendo una respuesta memorizada.

Answer 3

Pasos:

1. Copiar datos de Nodo (i + 1) al nodo (i)
2. Copiar el SIGUIENTE de segundo nodo (i + 1) en una variable temporal.
3. Ahora elimine el segundo nodo (i + 1) // no requiere el puntero al nodo anterior.

Función:

void delete_node(node* node) 
{ 
    node->Data = node->Next->Data; 
    node* temp = node->Next->Next; 
    delete(node->Next); 
    node->Next = temp; 
} 

Answer 4

Probablemente podría necesitar su lista de enlaces de desplazamiento a asumir que cualquier nodo que apunta a null es null nodo independientemente del valor ...

a->b->c->d->NULL 

por lo d es null nodo y el nodo no se debe considerar como un nodo. de esta manera puede ahorrar al usar valores especiales ya que no son correctos en un sentido genérico. Aparte de eso, no tendrá otra forma para que el nodo anterior apunte al null.

Answer 5

luego debe haber un programa de verificación en el programa si el nodo dado es el último nodo o no.

void delete_node(node* node1) 
{ 
    node* search=head; 
    if(node1==head) 
    { 
     head=head->next; 
     search->next=NULL; 
     node1->next=NULL; 
    } 
    while(search->next != node1) 
     search=search->next; 
    if(node1->next==NULL) 
    { 
     search->next=NULL; 
    } 
    else 
    { 
     search->next=node1->next; 
     node1->next=NULL; 
    } 
    delete node1; 
} 

Answer 6

public void removeNode(Node node){ 

     /* if no node return null */ 
     if(node==null) return; 

     /* if only 1 node then delete node */ 
     if(node.getNext()==null) { 
      node = null; 
      return ; 
     } 

     /* copy next node data to this node */ 
     node.data = node.getNext().data(); 

     /* store the next next node */ 
     Node second = node.getNext().getNext(); 

     /* remove next node */ 
     removeNode(node.getNext()); 

     /* set the copied node as next */ 
     node.setNext(second); 
    } 

Answer 7

void deleteNode(Node * ptr) 
{ 
    Node *temp = ptr; 
    ptr = ptr->next; 
    temp->data = ptr->data; 
    temp->next = ptr->next; 
    free(ptr); 
} 

que no son capaces de atravesar la lista simplemente enlazada dirección hacia atrás. Eliminar nodo significa liberar esa memoria. Así que simplemente copie el siguiente contenido del nodo en el Puntero dado (dirección de memoria) y libere el siguiente nodo. Resolvería su problema. Gracias.