1

例如，有一个练习说：

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

这是解决方案：

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

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

4

3 回答 3

8

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

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

于 2013-08-07T07:20:46.890 回答
3

不，单链表是不可能的。

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

通常，您不能从仅给出指向该节点的指针的单链表中删除该节点。

您当前所做的基本上是“作弊”，因为您并没有真正删除指向的节点。您正在改变列表，然后删除指向的节点的后继节点。当您调用此函数时，如果某处的其他代码位持有指向该后继程序的指针，这会有所不同——它们的指针无效。因此，您要删除指向的数据元素，但不会删除指向的节点。

于 2013-08-07T07:18:10.863 回答
2

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

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

你需要一个指向列表第一个元素的指针，否则由于数据结构的性质，你不可能做你想做的事。

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

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

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

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

于 2013-08-07T07:38:11.260 回答