simples - Eliminar un nodo intermedio de una sola lista vinculada cuando el puntero al nodo anterior no está disponible

operaciones con listas enlazadas

Question

¿Es posible eliminar un nodo intermedio en la lista de enlaces individuales cuando la única información disponible que tenemos es el puntero al nodo que se va a eliminar y no el puntero al nodo anterior? Después de la eliminación, el nodo anterior debe apuntar al nodo junto a nodo eliminado

Answer 1

Aprecio el ingenio de esta solución (eliminar el siguiente nodo), pero no responde la pregunta del problema. Si esta es la solución real, la pregunta correcta debería ser "eliminar de la lista vinculada el VALOR contenido en un nodo en el que se asigna el puntero". Pero, por supuesto, la pregunta correcta te da una pista sobre la solución. El problema tal como está formulado tiene la intención de confundir a la persona (lo que de hecho me ha sucedido, especialmente porque el entrevistador ni siquiera mencionó que el nodo está en el medio).

Answer 2

Dado

A -> B -> C -> D

y un puntero a, digamos, el elemento B, lo eliminaría
1. liberar cualquier memoria perteneciente a miembros de B
2. copia el contenido de C en B (esto incluye su puntero "siguiente")
3. eliminar todo el elemento C

Por supuesto, tendrá que tener cuidado con los casos extremos, como trabajar en listas de un elemento.

Ahora donde estaba B, tiene C y se libera el almacenamiento que solía ser C.

Answer 3

Definitivamente es más una prueba que un problema real. Sin embargo, si se nos permite hacer alguna suposición, se puede resolver en O (1) vez. Para hacerlo, las restricciones a las que apunta la lista deben ser copiables. El algoritmo es como el siguiente:

Tenemos una lista parecida a: ... -> Nodo (i-1) -> Nodo (i) -> Nodo (i + 1) -> ... y necesitamos eliminar el Nodo (i).

1. Copie los datos (no el puntero, los datos mismos) del Nodo (i + 1) al Nodo (i), la lista se verá como: ... -> Nodo (i-1) -> Nodo (i + 1) -> Nodo (i + 1) -> ...
2. Copie el PRÓXIMO del segundo nodo (i + 1) en una variable temporal.
3. Ahora elimine el segundo nodo (i + 1), no requiere puntero al nodo anterior.

Pseudocódigo:

void delete_node(Node* pNode)
{
    pNode->Data = pNode->Next->Data;  // Assume that SData::operator=(SData&) exists.
    Node* pTemp = pNode->Next->Next;
    delete(pNode->Next);
    pNode->Next = pTemp;
}

Micro.

Answer 4

El mejor enfoque es copiar los datos del siguiente nodo en el nodo que se va a eliminar, establecer el siguiente puntero del nodo al siguiente puntero del siguiente nodo y eliminar el siguiente nodo.

Los problemas de los punteros externos que apuntan al nodo que se eliminará, aunque son verdaderos, también se mantendrían para el siguiente nodo. Considere las siguientes listas enlazadas:

A-> B-> C-> D-> E-> F y G-> H-> I-> D-> E-> F

En caso de que tenga que eliminar el nodo C (en la primera lista vinculada), mediante el enfoque mencionado, eliminará el nodo D después de copiar el contenido al nodo C. Esto dará como resultado las siguientes listas:

A-> B-> D-> E-> F y G-> H-> I-> puntero colgante.

En caso de que elimine por completo el NODE C, las listas resultantes serán:

A-> B-> D-> E-> F y G-> H-> I-> D-> E-> F.

Sin embargo, si va a eliminar el nodo D y utiliza el enfoque anterior, el problema de los indicadores externos aún está allí.

Answer 5

El siguiente código creará un LL, n luego le pedirá al usuario que dé el puntero al nodo que se eliminará. imprimirá la lista después de la eliminación. Hace lo mismo que se hace copiando el nodo después del nodo que se va a eliminar, sobre el nodo que se va a eliminar y luego elimina el siguiente nodo del nodo que se eliminará. es decir

a B C D

copia c a b y c libre de modo que el resultado es

acd

struct node  
{
    int data;
    struct node *link;
 };

void populate(struct node **,int);

void delete(struct node **);

void printlist(struct node **);

void populate(struct node **n,int num)
{

    struct node *temp,*t;
    if(*n==NULL)
    {
        t=*n;
        t=malloc(sizeof(struct node));
        t->data=num;
        t->link=NULL;
        *n=t;
    }
    else
    {
        t=*n;
        temp=malloc(sizeof(struct node));
        while(t->link!=NULL)
            t=t->link;
        temp->data=num;
        temp->link=NULL;
        t->link=temp;
    }
}

void printlist(struct node **n)
{
    struct node *t;
    t=*n;
    if(t==NULL)
        printf("/nEmpty list");

    while(t!=NULL)
    {
        printf("/n%d",t->data);
        printf("/t%u address=",t);
        t=t->link;
    }
}


void delete(struct node **n)
{
    struct node *temp,*t;
    temp=*n;
    temp->data=temp->link->data;
    t=temp->link;
    temp->link=temp->link->link;
    free(t);
}    

int main()
{
    struct node *ty,*todelete;
    ty=NULL;
    populate(&ty,1);
    populate(&ty,2);
    populate(&ty,13);
    populate(&ty,14);
    populate(&ty,12);
    populate(&ty,19);

    printf("/nlist b4 delete/n");
    printlist(&ty);

    printf("/nEnter node pointer to delete the node====");
    scanf("%u",&todelete);
    delete(&todelete);

    printf("/nlist after delete/n");
    printlist(&ty);

    return 0;
}

Answer 6

Esta es una pieza de código que armé y que hace lo que el OP estaba pidiendo, e incluso puede eliminar el último elemento de la lista (no de la manera más elegante, pero lo hace). Lo escribió mientras aprendía a usar listas enlazadas. Espero eso ayude.

#include <cstdlib>
#include <ctime>
#include <iostream>
#include <string>

using namespace std;


struct node
{
    int nodeID;
    node *next;
};

void printList(node* p_nodeList, int removeID);
void removeNode(node* p_nodeList, int nodeID);
void removeLastNode(node* p_nodeList, int nodeID ,node* p_lastNode);

node* addNewNode(node* p_nodeList, int id)
{
    node* p_node = new node;
    p_node->nodeID = id;
    p_node->next = p_nodeList;
    return p_node;
}

int main()
{
    node* p_nodeList = NULL;
    int nodeID = 1;
    int removeID;
    int listLength;
    cout << "Pick a list length: ";
    cin >> listLength;
    for (int i = 0; i < listLength; i++)
    {
        p_nodeList = addNewNode(p_nodeList, nodeID);
        nodeID++;
    }
    cout << "Pick a node from 1 to " << listLength << " to remove: ";
    cin >> removeID;
    while (removeID <= 0 || removeID > listLength)
    {
        if (removeID == 0)
        {
            return 0;
        }
        cout << "Please pick a number from 1 to " << listLength << ": ";
        cin >> removeID;
    }
    removeNode(p_nodeList, removeID);
    printList(p_nodeList, removeID);
}

void printList(node* p_nodeList, int removeID)
{
    node* p_currentNode = p_nodeList;
    if (p_currentNode != NULL)
    {
        p_currentNode = p_currentNode->next;
        printList(p_currentNode, removeID);
        if (removeID != 1)
        {
            if (p_nodeList->nodeID != 1)
            {
                cout << ", ";
            }

            cout << p_nodeList->nodeID;
        }
        else
        {
            if (p_nodeList->nodeID !=2)
            {
                cout << ", ";
            }
            cout << p_nodeList->nodeID;
        }
    }
}

void removeNode(node* p_nodeList, int nodeID)
{
    node* p_currentNode = p_nodeList;
    if (p_currentNode->nodeID == nodeID)
    {
        if(p_currentNode->next != NULL)
        {
            p_currentNode->nodeID = p_currentNode->next->nodeID;
            node* p_temp = p_currentNode->next->next;
            delete(p_currentNode->next);
            p_currentNode->next = p_temp;
        }
        else
        {
            delete(p_currentNode);
        }
    }
    else if(p_currentNode->next->next == NULL)
    {
        removeLastNode(p_currentNode->next, nodeID, p_currentNode);
    }
    else
    {
        removeNode(p_currentNode->next, nodeID);
    }
}

void removeLastNode(node* p_nodeList, int nodeID ,node* p_lastNode)
{
    node* p_currentNode = p_nodeList;
    p_lastNode->next = NULL;
    delete (p_currentNode);
}

Answer 7

Imposible.

Hay hacks para imitar la eliminación.

Pero ninguno de ellos eliminará el nodo al que apunta el puntero.

La popular solución de eliminar el siguiente nodo y copiar su contenido al nodo real que se va a eliminar tiene efectos secundarios si tiene punteros externos que apuntan a los nodos de la lista, en cuyo caso un puntero externo que apunta al siguiente nodo quedará colgando.

Answer 8

La única forma sensata de hacerlo es recorrer la lista con un par de punteros hasta que el líder encuentre el nodo que se va a eliminar, luego actualice el siguiente campo con el puntero final.

Si desea eliminar elementos aleatorios de una lista de manera eficiente, debe estar doblemente vinculado. Sin embargo, si desea tomar elementos del encabezado de la lista y agregarlos en la cola, no necesita vincular doblemente toda la lista. Haga un enlace sencillo a la lista, pero haga que el siguiente campo del último elemento en la lista apunte al primer elemento de la lista. Luego, haga que la lista "cabeza" apunte al artículo de cola (no a la cabeza). Luego es fácil agregarlo a la cola de la lista o quitarlo de la cabeza.

Answer 9

La sugerencia inicial fue transformar:

a -> b -> c

a:

a ->, c

Si mantiene la información alrededor, por ejemplo, un mapa de la dirección del nodo a la dirección del próximo nodo, entonces puede arreglar la cadena la próxima vez para recorrer la lista. Si necesita eliminar varios elementos antes del siguiente cruce, debe realizar un seguimiento del orden de las eliminaciones (es decir, una lista de cambios).

La solución estándar es considerar otras estructuras de datos como una lista de omisiones.

Answer 10

No si desea mantener la capacidad de transferencia de la lista. Necesita actualizar el nodo anterior para vincularlo al siguiente.

¿Cómo terminaste en esta situación, de todos modos? ¿Qué estás tratando de hacer que te hace esta pregunta?

Answer 11

Para llegar al elemento de la lista anterior, deberá recorrer la lista desde el principio hasta que encuentre una entrada con el next puntero que apunta a su elemento actual. Luego, tendría un puntero a cada uno de los elementos que tendría que modificar para eliminar el elemento actual de la lista: simplemente configure previous->next to current->next then delete current .

editar: ¡Kimbo me ganó en menos de un minuto!

Answer 12

Podría hacer una desvinculación retrasada en la que establezca los nodos para desvincularlos de la lista con un indicador y luego eliminarlos en el siguiente cruce adecuado. Los nodos configurados para desvincularse deben ser manejados correctamente por el código que rastrea la lista.

Supongo que también podrías recorrer la lista nuevamente desde el principio hasta que encuentres lo que apunta a tu artículo en la lista. Difícilmente óptimo, pero al menos una idea mucho mejor que la desvinculación retrasada.

En general, debe conocer el puntero del artículo del que acaba de salir y debe pasarlo por alto.

(Edit: Ick, con el tiempo que tardé en escribir una respuesta completa, tres millones de personas cubrieron casi todos los puntos que iba a mencionar) :()

Answer 13

Sí, pero su lista se romperá después de eliminarla.

En este caso específico, recorra la lista nuevamente y obtenga ese puntero! En general, si hace esta pregunta, probablemente exista un error en lo que está haciendo.

Answer 14

Si tiene una lista vinculada A -> B -> C -> D y un puntero al nodo B. Si tiene que eliminar este nodo, puede copiar el contenido del nodo C en B, el nodo D en C y eliminar D. no podemos eliminar el nodo como tal en el caso de una lista enlazada individualmente, ya que si lo hacemos, el nodo A también se perderá. Aunque podemos retroceder a A en caso de una lista doblemente vinculada.

¿Estoy en lo cierto?

Answer 15

Supongamos una lista con la estructura

A -> B -> C -> D

Si solo tenía un puntero a B y deseaba eliminarlo, podría hacer algo como

tempList = B->next;
*B = *tempList;
free(tempList);

La lista se vería así

A -> B -> D

pero B mantendría los contenidos anteriores de C, eliminando de manera efectiva lo que estaba en B. Esto no funcionará si algún otro código contiene un puntero a C. Tampoco funcionará si intentas eliminar el nodo D. Si desea realizar este tipo de operación, deberá compilar la lista con un nodo ficticio de cola que no se utiliza realmente, por lo que garantiza que ningún nodo útil tendrá un próximo puntero NULL. Esto también funciona mejor para listas donde la cantidad de datos almacenados en un nodo es pequeña. Una estructura como

struct List { struct List *next; MyData *data; };

estaría bien, pero uno donde es

struct HeavyList { struct HeavyList *next; char data[8192]; };

sería un poco molesto

Answer 16

Tal vez hacer una eliminación suave? (es decir, establezca un indicador "eliminado" en el nodo) Puede limpiar la lista más adelante si es necesario.

Answer 17

Tendrás que marchar hacia abajo en la lista para encontrar el nodo anterior. Eso hará que borrar en general O (n ** 2). Si es el único código que realiza eliminaciones, puede hacerlo mejor en la práctica almacenando en caché el nodo anterior y comenzando su búsqueda allí, pero si esto ayuda depende del patrón de eliminaciones.

Answer 18

Un enfoque sería insertar un nulo para los datos. Cada vez que recorre la lista, realiza un seguimiento del nodo anterior. Si encuentra datos nulos, arregle la lista y vaya al siguiente nodo.

Answer 19

Usted tiene el jefe de la lista, ¿verdad? Usted acaba de atravesarlo.

Digamos que su lista está apuntada por "cabeza" y el nodo para eliminarla "del".

Pseudocódigo de estilo C (los puntos serían -> en C):

prev = head
next = prev.link

while(next != null)
{
  if(next == del)
  {
    prev.link = next.link;
    free(del);
    del = null;
    return 0;
  }
  prev = next;
  next = next.link;
}

return 1;

Answer 20

sí, pero no puedes desvincularlo. Si no te importa corromper la memoria, adelante ;-)

Answer 21

Void deleteMidddle(Node* head)
{
     Node* slow_ptr = head;
     Node* fast_ptr = head;
     Node* tmp = head;
     while(slow_ptr->next != NULL && fast_ptr->next != NULL)
     {
        tmp = slow_ptr;
        slow_ptr = slow_ptr->next;
        fast_ptr = fast_ptr->next->next;
     }
     tmp->next = slow_ptr->next;
     free(slow_ptr);
    enter code here

}

Answer 22

void delself(list *list)
{
   /*if we got a pointer to itself how to remove it...*/
   int n;

   printf("Enter the num:");

   scanf("%d",&n);

   while(list->next!=NULL)
   {
       if(list->number==n) /*now pointer in node itself*/
       {
           list->number=list->next->number;
           /*copy all(name,rollnum,mark..) data of next to current, disconect its next*/
           list->next=list->next->next;
       }
       list=list->next;
   }
}

Answer 23

void delself(list *list)
{
   /*if we got a pointer to itself how to remove it...*/
   int n;

   printf("Enter the num:");
   scanf("%d",&n);

   while(list->next!=NULL)
   {
      if(list->number==n) /*now pointer in node itself*/
      {
         list->number=list->next->number;   /*copy all(name,rollnum,mark..)
                             data of next to current, disconnect its next*/
         list->next=list->next->next;
      }
      list=list->next;
   }
}