c++ - 从单链表中删除最后一个节点

Question

我必须编写一个方法来删除列表中的最后一个节点。你们对我应该如何处理这个问题有什么想法吗？

Answer 1

如果你有一个单链表，你别无选择，只能遍历整个列表到最后一个节点，维护一个指向前一个节点的指针，这样你就可以重置它的 next 字段释放最后一个节点:

if (head)
{
    node *curNode = head;
    node *prevNode = NULL;

    while (curNode->next)
    {
        prevNode = curNode;
        curNode = curNode->next;
    }

    if (prevNode) prevNode->next = NULL;
    delete curNode;
}

如果您改用双链表，这会更容易，因为您可以保留指向列表中最后一个节点的指针并直接对其进行操作:

if (head == tail)
{
    delete head;
    head = tail = NULL;
}
else if (tail)
{
    node *curNode = tail;
    tail = curNode->previous; 
    tail->next = NULL;
    delete curNode;
}

当然，如果您真的使用 C++，那么您应该使用 STL 的 std::list(双链接)或 std::forward_list(单链接) linked) 容器，它会为你处理这些细节。