删除链接列表中所有出现的项目

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