c - 从给定位置的链表中删除一个元素

Question

我有一个关于从链表中删除元素的简单问题。我试图完成的工作与我在网上看到的代码之间的唯一区别是，我试图删除一个元素，给定一个位置，而不是给定需要删除的实际元素。

任何帮助表示赞赏。

Answer 1

可以在 O(1) 时间内完成删除链表中给定指针的节点。我们不必进行遍历。

我假设你的位置是指给定节点的指针：

可以说node是需要删除的元素。

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

但是如果位置表示列表中的第 n 个元素，唯一的方法是遍历该(n-1)th元素并删除下一个元素（链表中的常规删除）：

Node* temp = previous->next;
previous->next = temp->next;
free(temp);

这都是假设链表是一个基于指针的链表

Answer 2

您可以这样做，这是示例程序，它可以根据您作为参数提供的索引删除任何节点。

start -> 指向第一个节点
traverse -> 指向要删除的 节点
traverseNext -> 指向要删除的前一个节点。

代码如下所示。

     #include <iostream>

     struct myList
     {
       int data;
   struct myList *next;
      };

    struct myList *start=NULL;  

    //this method removes a node from the position index
    void remove(int index)
    {
           myList *traverse = start;    
           myList *traverseNext = NULL;

           int i = 1;   
          while(i<(index-1))
           {
                  traverse = traverse->next;
          i++;
           }
              traverseNext = traverse;
          traverse = traverse->next;
          if(traverse->next == NULL)
          {     
         delete traverse;
         traverseNext->next = NULL;
         traverse = NULL;
          return;
           }

             else
          {     
          traverseNext->next = traverse->next;
          delete traverse;
          traverse = NULL;
           return;
           }

    }




int main(void)
   {
      myList *node1;
      myList *node2;    
      myList *node3;    

         node1 = new myList;    
         node2 = new myList;    //Created 3 nodes of type myList
         node3 = new myList;    

         node1->data = 10;
         node1->next = node2;


         node2->data = 20;
         node2->next = node3;


         node3->data = 30;
         node3->next = NULL;

         start = node1;     //start is pointing to node1
         remove(2);      //removing the node 2, so the output will be 10 30
        while(start)  //iterating through all the nodes from start, since start
       {              //is pointing to the first node.
    std::cout<<start->data<<" ";
    start = start->next;

           }
    } 

Answer 3

如果要删除多个项目，可以先遍历列表，然后将要删除的所有项目收集到另一个列表中。然后只需在收集的列表中调用“removeAll”即可。

Answer 4

查找列表直到找到第 n 个元素（使用计数器），然后更新前一个节点的next指针以指向您当前所在的节点之后的指针（有效地删除它）。如果您也在使用它们，请调整前一个指针。

Answer 5

这很简单：

1）通过遍历列表找到第 N 个项目，另外使用计数器来跟踪您是哪个节点。

2）删除该节点，就像你删除任何其他链表一样。

Answer 6

#include <stdio.h>
#include <stdlib.h>

typedef struct element{
    int num;
    struct element * next;
} element;

void delNth(element **header, int pos){//pos : zero origin
    element *prev, *tmp;
    int i;

    if(header == NULL || *header == NULL || pos < 0) return ;
    if(pos == 0){
        tmp = (*header)->next;
        free(*header);
        *header = tmp;
    } else {
        prev = *header;
        tmp = (*header)->next;
        for(i=1;i<pos;++i){
            prev = tmp;
            tmp = tmp->next;
            if(tmp == NULL) return ;//or rise error
        }
        prev->next = tmp->next;
        free(tmp);
    }
}

void drop(element *header){
    if(header){
        drop(header->next);
        free(header);
    }
}

void printList(element *header){
    while (header!=NULL){
        printf("%d ",header->num);
        header=header->next;
    }
    printf("\n");
}

int main(int argc, char **argv){
    int pos = atoi(argv[1]);
    element *a;
    element *b;
    element *c;

    a=malloc(sizeof(element));
    b=malloc(sizeof(element));
    c=malloc(sizeof(element));
    a->num=5;
    b->num=6;
    c->num=7;
    a->next=b;
    b->next=c;
    c->next=NULL;

    printList(a);

    delNth(&a, pos);

    printList(a);

    drop(a);

    return 0;
}
/* execute result
>a 0
5 6 7
6 7

>a 1
5 6 7
5 7

>a 2
5 6 7
5 6

>a 3
5 6 7
5 6 7
*/