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

Question

Можно ли удалить средний узел в единственном связанном списке, когда единственная доступная нам информация - это указатель на удаляемый узел, а не указатель на предыдущий узел? После удаления предыдущий узел должен указывать на узел рядом с удаленным узлом.

Answer 1

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

Как ты попал в такую ​​ситуацию? Что вы пытаетесь сделать, чтобы вы задали этот вопрос?

Answer 2

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

Допустим, на ваш список указывает «голова», а узел для его удаления - «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;

Answer 3

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

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

Answer 4

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

Я прав?

Answer 5

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

Answer 6

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 7

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

A-B-C-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;
}

Answer 8

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 9

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

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

Answer 10

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

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

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

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