从链接列表中删除节点

Question

我正在从迭代删除功能，从链表中删除节点，我认为代码应该工作正常，它遍历列表，找到所需的节点，指向头到下一个节点，并删除当前，但是当我试运行它，我得到无限循环，可以请你帮我查明错误，这里是功能：

typedef struct E_Type * List; 
struct E_Type 
{ 
    int data; 
    struct E_Type* next; 
}; 

功能：

bool erase(List & l, int data){ 
List head = l; 
if (l != 0){ 
    for(List current = head; current; current = current->next){ 
    if (current->data == data) 
     head = current->next; 
     delete current; 
     return true; 
    } 
    } 
return false; 
} 

测试程序：

int main() 
{ 
    List l = 0; 
    cout << boolalpha << l->data << "went well? "<< (insert(l,73)) << endl; 
    cout << boolalpha << l->data << "went well? "<< (insert(l,24)) << endl; 
    print(cout,l); 
    cout << boolalpha << "Is deleted 24? "<<(erase(l,24)) << endl;  
    cout << boolalpha << "Is deleted 35? "<<(erase(l,35)) << endl; 
    print(cout,l); 
    cout << endl; 
    return 0; 
} 

插入：

bool insert(List & l, int data) 
{ 

    List current = l; 
    while(current != 0) { 
     if (current->data == data) 
     return false; 
     current = current->next; 
    } 

    if (l == 0 || l->data > data){ 
     List new_list = new E_Type; 
     new_list->data = data; 
     new_list->next = l; 
     l = new_list; 
    return true; 
    } 

    else if(l->data < data){ 
    insert(l->next, data); 
    return true; 
    } 

} 

Answer 1

正如Andreas Brinck已经指出的那样，您还需要更新'上一个'链接。不过，你不需要为这个专门的变量，只要用一个指针的指针：

bool erase(List & l, int data){ 
    List *it = &l; 
    while (*it) { 
    if ((*it)->data == data) { 
     List next = (*it)->next; 
     delete *it; 
     *it = next; 
     return true; 
    } 
    it = &(*it)->next; 
    } 
    return false; 
} 

这也需要谨慎的处理所有的“特殊情况”，比如从空的列表中删除，删除列表中的第一个元素或删除列表中的最后一个元素。

Answer 2

我们可能需要看到您的插入方法为好。

难道

current == current->next 

如果是的话，可能会导致无限循环。

Answer 3

您需要在跟踪前一个节点，以及用于循环，这样做：

prev->next = current->next; 
delete current; 

您还需要处理的就是删除元素是第一要素的情况下列表，在这种情况下，你需要设置l到l->next

bool erase(List & l, int data){ 
if (l != 0){ 
    for(List current = head, prev = 0; current; prev = current, current = current->next){ 
    if (current->data == data) 
    { 
     if (prev) 
     { 
      prev->next = current->next; 
     } 
     else 
     { 
      l = current->next; 
     } 
     delete current; 
     return true; 

    } 
    } 
return false; 
} 

你的第一擦除可能创建一个循环链表现在。