從給定位置的鏈表中刪除元素

Question

我有一個關於從鏈表中刪除元素的簡單問題。我試圖完成的工作和我在線上看到的代碼之間的唯一區別是，我試圖刪除一個給定位置的元素，而不是給出需要刪除的實際元素。

任何幫助表示讚賞。

Answer 1

你可以這樣做，下面是一個示例程序，它可以根據你提供的索引刪除任何節點作爲論證。

開始 - >指向到第一節點
橫移 - >指向其具有將被刪除的節點
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

查找列表，直到找到第n個元素（使用計數器），然後更新上一個節點的下一個指針指向當前所在的那個指針（有效地將其刪除）。如果您也使用它們，請調整以前的指針。

Answer 3

這很簡單：

1）通過列表迭代，另外使用一個計數器來跟蹤你是哪個節點一個找到第N項。

2）刪除該節點，就像其他鏈接列表一樣。

Answer 4

如果你想刪除多個項目，你可以先遍歷列表，然後收集你想要刪除的所有項目到另一個列表。然後簡單地調用'removeAll'傳入收集的列表。

Answer 5

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

Answer 6

在刪除到的指針被給定一個鏈表中的節點可以在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); 

這是假設鏈表是一個基於指針的鏈表