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

Question

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

感谢您的帮助。

Answer 1

您可以做到这一点，下面是示例程序，它可以根据您作为argumenT提供的索引删除任何节点。

start->指向第一个节点
遍历->指向必须删除的节点
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 2

删除链表中给定指针的节点可以在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 3

这很简单：

1） 通过迭代列表来定位第N个项目，此外还使用计数器来跟踪您是哪个节点。

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

Answer 4

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

Answer 5

如果要删除多个项目，可以先遍历列表，然后将要删除的所有项目收集到另一个列表中。然后简单地调用传入已收集列表的removeAll。

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
*/