Удаление среднего node из одного связанного списка, когда указатель на предыдущий node недоступен

Ответ 1

Это определенно скорее опрос, а не настоящая проблема. Однако, если нам разрешено сделать какое-то предположение, оно может быть разрешено в O (1) раз. Чтобы сделать это, ограничители списка должны быть скопируемыми. Алгоритм выглядит следующим образом:

У нас есть список, похожий на:... → Node (i-1) → Node (i) → Node (i + 1) → ... и нам нужно delete Node (i).

• Скопировать данные (не указатель, сами данные) из Node (i + 1) в Node (i), список будет выглядеть так:... → Node (i-1) → Node (i + 1) → Node (i + 1) → ...
• Скопируйте NEXT второго Node (i + 1) во временную переменную.
• Теперь удалите второй Node (i + 1), он не требует указателя на предыдущий node.

псевдокод:

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;
}

Майк.

Ответ 2

Предположим, что список со структурой

A → B → C → D

Если у вас есть указатель на B и вы хотите удалить его, вы можете сделать что-то вроде

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

После этого список будет выглядеть как

A → B → D

но B сохранит старое содержимое C, эффективно удалив то, что было в B. Это не сработает, если какой-либо другой фрагмент кода содержит указатель на C. Он также не будет работать, если вы пытаетесь удалить node D. Если вы хотите выполнить такую ​​операцию, вам нужно будет создать список с фиктивным хвостом node, который не используется, поэтому вы гарантируете, что никакой полезный node не будет иметь следующий указатель NULL. Это также лучше работает для списков, где количество данных, хранящихся в node, невелико. Структура, подобная

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

будет в порядке, но там, где находится

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

будет немного обременительным.

Ответ 3

Невозможно.

Есть хаки, имитирующие удаление.

Но ни один из них на самом деле не удалит node указатель, указывающий на.

Популярное решение об удалении следующего node и копирования его содержимого в фактический node, который будет удален, имеет побочные эффекты, если у вас есть внешние указатели, указывающие на узлы в списке, и в этом случае внешний указатель, указывающий на следующий node, станет свисающим.

Ответ 4

Я ценю изобретательность этого решения (удаление следующего node), но оно не отвечает на вопрос проблемы. Если это фактическое решение, правильным вопросом должно быть "удалить из связанного списка значение VALUE, содержащееся в node, на котором указан указатель". Но, конечно, правильный вопрос дает вам подсказку о решении. Проблема, как она сформулирована, предназначена для того, чтобы запутать человека (что на самом деле произошло со мной, особенно потому, что интервьюер даже не упомянул, что node находится посередине).

Ответ 5

Один из подходов - вставить нуль для данных. Всякий раз, когда вы проходите список, вы отслеживаете предыдущий node. Если вы найдете нулевые данные, вы исправите список и перейдите к следующему node.

Ответ 6

Лучше всего по-прежнему копировать данные следующего node в node для удаления, установить следующий указатель node на следующий node следующий указатель и удалить следующий node.

Проблемы с внешними указателями, указывающими на node, которые будут удалены, а true, также будут сохраняться для следующего node. Рассмотрим следующие связанные списки:

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

В случае, если вам нужно удалить node C (в первом связанном списке), упомянутым подходом, вы удалите node D после копирования содержимого на node C. Это приведет к следующим спискам

A- > B- > D- > E- > F и G- > H- > I- > висячий указатель.

Если вы полностью удалите node C, результирующие списки будут следующими:

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

Однако, если вы хотите удалить node D, и вы используете более ранний подход, проблема внешних указателей по-прежнему существует.

Ответ 7

Первоначальное предложение состояло в том, чтобы преобразовать:

a → b → c

в

a → , c

Если вы храните информацию вокруг, скажем, карты с адреса node, на адрес следующего node, тогда вы можете исправить цепочку в следующий раз, чтобы пройти по списку. Если вам нужно удалить несколько элементов до следующего обхода, вам необходимо отслеживать порядок удалений (т.е. Список изменений).

Стандартное решение рассматривает другие структуры данных, такие как список пропусков.

Ответ 8

Может быть, сделать мягкое удаление? (т.е. установить "удаленный" флаг в node). Вы можете очистить список позже, если вам нужно.

Ответ 9

Нет, если вы хотите поддерживать прослеживаемость списка. Вам необходимо обновить предыдущий node, чтобы перейти к следующему.

Как вы в конечном итоге оказались в этой ситуации? Что вы пытаетесь сделать, это заставляет вас задавать этот вопрос?

Ответ 10

Вам нужно будет пометить список, чтобы найти предыдущий node. Это приведет к удалению вообще O (n ** 2). Если вы являетесь единственным удалением кода, вы можете сделать это на практике лучше, кэшируя предыдущий node и начинать поиск там, но зависит ли это от шаблона удалений.

Ответ 11

Учитывая

A → B → C → D

и указатель на, скажем, элемент B, вы должны удалить его с помощью 1. освободить любую память, принадлежащую членам B
2. скопируйте содержимое C в B (сюда входит его "следующий" указатель)
3. удалить весь элемент C

Конечно, вам нужно быть осторожным в отношении крайних случаев, таких как работа над списками одного элемента.

Теперь, когда был B, у вас есть C, и хранилище, которое раньше было C, было освобождено.

Ответ 12

да, но вы не можете его обмануть. Если вы не заботитесь о развращении памяти, продолжайте: -)

Ответ 13

Да, но ваш список будет поврежден после его удаления.

В этом конкретном случае перейдите в список снова и получите этот указатель! В общем, если вы задаете этот вопрос, вероятно, существует ошибка в том, что вы делаете.

Ответ 14

Чтобы перейти к предыдущему элементу списка, вам нужно будет пересечь список с самого начала, пока не найдете запись с указателем next, который указывает на ваш текущий элемент. Тогда у вас будет указатель на каждый из элементов, которые вам нужно будет изменить, чтобы удалить текущий элемент из списка - просто установите previous->next в current->next, затем удалите current.

edit: Кимбо избил меня к ней менее чем за минуту!

Ответ 15

Вы могли бы задерживать деление, когда вы устанавливаете узлы для выделения из списка с флагом, а затем удаляете их при следующем правильном обходе. Узлы, которые должны быть деинсталлированы, должны быть надлежащим образом обработаны с помощью кода, который сканирует список.

Я полагаю, вы могли бы просто просто пройти список с самого начала, пока не найдете то, что указывает на ваш элемент в списке. Вряд ли оптимальная, но, по крайней мере, гораздо лучшая идея, чем отсрочка.

В общем, вы должны знать указатель на элемент, из которого вы только что пришли, и вы должны его пропустить.

(Edit: Ick, со временем, когда мне понадобилось, чтобы набрать полный ответ, три человека были покрыты почти всеми пунктами, которые я собирался упомянуть.:()

Ответ 16

Единственный разумный способ сделать это - пересечь список с помощью нескольких указателей, пока ведущий не найдет node, а затем обновит следующее поле, используя трейлинг-указатель.

Если вы хотите эффективно удалять случайные элементы из списка, он должен быть дважды связан. Если вы хотите брать предметы из головы списка и добавить их в хвост, однако вам не нужно дважды связывать весь список. Одинаково свяжите список, но сделайте следующее поле последнего элемента в списке, указывающем на первый элемент в списке. Затем сделайте список "голова" точкой для элемента хвоста (а не головы). Затем легко добавить в хвост списка или удалить из головы.

Ответ 17

У вас есть глава списка, не так ли? Вы просто проходите его.

Скажем, что на ваш список указали "head" и node, чтобы удалить его "del".

Псевдокод стиля C (точки будут → в 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;

Ответ 18

Следующий код создаст LL, n затем попросит пользователя указать указатель на node для удаления. он распечатает список после удаления Он делает то же самое, что и при копировании node после удаления node по node, который необходимо удалить, а затем удалить следующий node из node, который нужно удалить. то есть

а-б-с-d

скопируйте c в b и освободите c, чтобы результат

а-с-d

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;
}

Ответ 19

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;
   }
}

Ответ 20

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;
   }
}

Ответ 21

Если у вас есть связанный список A → B → C → D и указатель на node B. Если вам нужно удалить этот node, вы можете скопировать содержимое node C в B, node D на C и удалить D. Но мы не можем удалить node как таковой в случае односвязного списка, поскольку, если мы это сделаем, node A также будет потерян. Хотя мы можем вернуться к A в случае двусвязного списка.

Я прав?

Ответ 22

Это фрагмент кода, который я собирал, который делает то, что запросил OP, и может даже удалить последний элемент в списке (не самым элегантным способом, но он его выполняет). Написал его, изучая, как использовать связанные списки. Надеюсь, что это поможет.

#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);
}

Ответ 23

Учитывая приведенный ниже список

1 → 2 → 3 → NULL

Указатель на узел 2, скажем, "ptr".

У нас может быть псевдокод, который выглядит примерно так:

struct node* temp = ptr->next;
ptr->data = temp->data;
ptr->next = temp->next;
free(temp);

Ответ 24

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

}