是否可以删除链接列表中的最后一个节点

Question

例如，有一个练习说：

编写一个函数，从链表中删除一个节点，只给定该指针

这就是解决方案：

void deleteNode(Node* toDelete) {
    // this function essensially first copies the data from the next pointer
    // and then, deletes the next pointer
    // However, it doesn't work if trying to delete the last element in the list
    Node *temp = toDelete->next;    // create a temp, assign to the one after toDelete
    toDelete->data = temp->data;    // change toDelete's data to the one's after it
    toDelete->next = temp->next;    // change toDelete's next to the one's after it
    delete temp;
    temp = nullptr;
}

如果只有指针的最后一个节点，我如何更改我的解决方案以删除链表中的最后一个元素？

Answer 1

显然不能；前一个节点指向一个有效的节点，没有办法更改它。

您可以做的是在列表的末尾添加一个sentinel节点。您永远不会删除该节点，也永远不会使用它来存储数据。然后，您的解决方案将适用于所有数据节点。这不需要对节点结构进行任何更改，但需要对迭代列表的方式进行更改。

Answer 2

不，使用单链表是不可能的。

原因是您需要修改倒数第二个节点（使其next指针为空）。但是没有办法从最后一个节点中找到那个节点。

通常，如果只给定指向节点的指针，则无法从单链表中删除节点。

你目前所做的基本上是一个"欺骗"，因为你并没有真正删除所指向的节点。你正在改变列表，然后删除所指向节点的后续节点。如果你调用这个函数时，某个地方的其他代码持有指向该后续节点的指针，那么它们的指针就会失效。因此，您删除了指向的数据元素，但没有删除指向的节点。

Answer 3

为了像这样处理单个链表中节点的删除，您需要在之前和之后修改节点。

            +-----+  +----------+  +------+
header----->|     |->| toDelete |->|      |
            +-----+  +----------+  +------+

您需要一个指向列表第一个元素的指针，因为否则，由于数据结构的性质，就不可能执行您想要的操作。

首先，您在需要删除的节点之前找到该节点，例如

Node* before = header;
for (;before->next != toDelete; before = before->next) {;}

现在执行before->next = toDelete->next，如果toDelete是最后一个节点，它将是一个nullptr，否则将是指向下一个节点的指针

（当然，在这两种情况下，您都需要删除toDelete指向的内容）