刪除鏈接列表中所有出現的項目

Question

下面的代碼將項目作爲參數並刪除鏈接列表中的所有項目。它與我的測試非常協調。有什麼我失蹤？這個代碼可以進一步改進嗎？

void 
LinkedList::DeleteAllOccurences(int key) { 
    Node *temp = head; 
    Node *prev = head; 
    while(temp!=NULL) { 
     if(temp->item == key){ 
     if(temp == head) { 
      head = temp->next; 
      delete temp; 
      temp = head; 
     } else { 
      prev->next = temp->next; 
      delete temp; 
      temp = prev->next; 
     } 
     } else { 
     prev = temp; 
     temp = temp->next; 
     } 
    } 
    return; 
} 

Answer 1

我相信你的代碼有一個bug。當刪除head節點時，prev未正確更新（即）它仍將指向刪除的頭節點。

我註釋你的代碼，並應用了修復[請原諒無償風格清理]：

void 
LinkedList::DeleteAllOccurences(int key) 
{ 
    Node *temp = head; 
    Node *prev = head; 

    while (temp != NULL) { 
     if (temp->item == key) { 
      // NOTE/BUG: after this, prev will _still_ be pointing to the 
      // _deleted_ head node 
      // NOTE/FIX: to fix this, prev must be set to the _updated_ head 
      // node 
      if (temp == head) { 
       head = temp->next; 

       // NOTE/FIX: add this: 
#if 1 
       prev = head; 
#endif 

       delete temp; 
       temp = head; 
      } 
      else { 
       prev->next = temp->next; 
       delete temp; 
       temp = prev->next; 
      } 
     } 
     else { 
      prev = temp; 
      temp = temp->next; 
     } 
    } 

    return; 
} 

有可能是另一個錯誤也是如此。而且，我認爲有一種方法可以簡化一些事情。因此，作比較：

void 
LinkedList::DeleteAllOccurences(int key) 
{ 
    Node *temp; 
    Node *prev = NULL; 
    Node *next; 

    for (temp = head; temp != NULL; temp = next) { 
     next = temp->next; 

     if (temp->item != key) { 
      prev = temp; 
      continue; 
     } 

     if (prev != NULL) 
      prev->next = next; 
     else 
      head = next; 

     delete temp; 
    } 
} 

Answer 2

另一種方法是使用std::list<>並讓它完成所有繁重工作。下面是一個應該適合您需要的示例實現：

#include <list> 
#include <iostream> 

using namespace std; 

int main() 
{ 
    // Create a list. 
    list<int> myList; 

    // Add some numbers: 2, 3, 2, and 5. 
    myList.push_back(2); 
    myList.push_back(3); 
    myList.push_back(2); 
    myList.push_back(5); 

    // Print the contents of the list. 
    // Will output 2, 3, 2, 5. 
    for(auto item : myList) 
     cout << item << endl; 

    // Remove all numbers equal to 2. 
    myList.remove(2); 

    // Print the contents of the list. 
    // Will output 3 and 5. 
    for(auto item : myList) 
     cout << item << endl; 

    return 0; 
}