c++ - 删除链表中的最后一个元素 (C++)

Question

我正在编写一个函数来删除链表中的最后一个节点。这就是我所拥有的，我在网上找到的其他代码搜索解决方案非常相似(我找到了几个)，但是当我执行它时，它会在删除链表的最后一个元素时创建某种无限循环(它删除其他元素就好了)。

这是我认为导致问题的代码:

void delete_final(Node* head){
    if(head == NULL) {
        return; }
    if(head->next == NULL) {
        delete head;
        head = NULL;
        return;
    }  
//other code 
}

我想这是内存问题(特别是在 delete head; 声明之后)，但我真的卡住了，希望能得到任何帮助或解释为什么这不起作用(我可能没有非常了解 C++ 中的指针和内存，我才刚刚开始)

这是我的节点代码供引用:

struct Node {
  int key;
  Node* next;
}; 

感谢您的帮助!

Answer 1

原代码:

void delete_final(Node* head){
    if(head == NULL) {
        return; }
    if(head->next == NULL) {
        delete head;
        head = NULL;
        return;
    }  
//other code 
}

没有指定“其他代码”，但如果列表只有一个节点，那么上面的代码将

• 删除第一个节点，然后

• 更新局部指针 head，它不会更新实际参数，因为它是按值传递。

在这种情况下，调用代码将留下一个悬挂指针，一个指向已销毁对象或此类对象曾经所在位置的指针。这种指针的任何使用都是未定义的行为。它可能看起来有效，或者崩溃，或者只是默默地让脏话纹身出现在你的额头上——任何……

---

一个解决方法是通过引用传递第一个指针:

void delete_final(Node*& head){
    if(head == nullptr) {
        return; }
    if(head->next == nullptr) {
        delete head;
        head = nullptr;
        return;
    }  
//other code 
}

---

处理链表的一个很好的辅助函数是unlink:

auto unlink( Node*& p )
    -> Node*
{
    Node* const result = p;
    p = p->next;
    return result;
}

实现 可能有点微妙，但使用它时您需要记住的是它会更新您作为参数传递的指针，该指针应该是第一个节点指针或 next 链表中的指针，并返回指向未链接节点的指针。

例如你可以做到

delete unlink( p_first );