我正在编写一个应该删除链表最后一个元素的函数
这是我对节点的定义
struct Node {
int key;
Node* next;
};
我有一个节点列表 1，它为值 1、2、3 运行 3 次插入函数
插入函数如下所示
void insert( Node*& head, int key) {
Node * curr = new Node;
curr->key = key;
curr->next = head;
head = curr;
}
现在我的delete_last_element函数看起来像这样
void delete_last_element( Node*& head )
{
Node *curr;
if (head == NULL)
return;
curr = head->next;
if (curr == NULL){
delete head;
head = NULL;
return;
}
head = curr;
while (curr->next != NULL) {
head = curr;
curr = curr->next;
}
delete head->next;
head -> next = NULL;
}
基本上我的想法是我首先看看第一个元素是否为空，如果是，那么我什么都不做，因为没有最后一个元素。然后我将 curr 设置为 head->next 以查看列表中的下一个元素，如果为 null，我将删除 head，因为我知道它是最后一个元素并返回。
现在我知道第一个元素不是最后一个元素，我将 head 分配给 curr 或第二个元素。从这里我进入 while 循环并检查下一个元素（从第三个开始）是否为 null，如果是，我删除当前元素，如果不是，我将头移动到下一个元素，然后检查之后的下一个元素。
现在我的链表最初以 3 2 1 开头，但无论出于何种原因，当我运行 delete_last_element 函数时，它变成了 2 而不是 3 2。
谁能告诉我我可能做错了什么？
谢谢
在这个例子中，你有两个条件需要注意：
- 列表为空。
- 列表中只有一个元素。
如果列表为空，则由指向 nullptr 的head指针指示。如果没有列表，则没有要删除的内容，因此我们可以退出函数：
if (head == nullptr)
return;
检查列表中是否只有一个元素很有用的原因是，如果我们保留两个指针来遍历列表 - 一个指向当前元素，另一个指向当前元素之前。删除当前节点后，"上一个"指针必须将其next指针设置为 nullptr。如果没有前一个节点（因为只有一个元素），那么我们就不能使用前一个指针。
if (!head->next)
{
delete head;
head = nullptr;
return;
}
node *prev = nullptr, // previous is nullptr
*curr = head; // start at head
现在我们必须遍历列表以找到最后一个元素。您不应该使用head来遍历列表，因为需要head来表示列表的开头，您不能让它指向其他任何地方，因此我们改用curr。
while (curr->next)
{
prev = curr;
curr = curr->next;
}
现在我们已经到达了列表的末尾，我们可以删除curr并将前面的指针next设置为 nullptr ：
delete curr;
prev->next = nullptr;
仅此而已。这是完整的方法：
void delete_last_element(node*& head)
{
if (head == nullptr) // list is empty, nothing to do
return;
if (head->next == nullptr) // only one element in list
{
delete head;
head = nullptr; // set back to nullptr
return; // get outta here
}
node *prev = nullptr,
*curr = head;
while (curr->next)
{
prev = curr;
curr = curr->next;
}
delete curr;
prev->next = nullptr;
}
这是一个演示，展示了它的用法。
一旦你理解了上面的代码，你就可以弄清楚如何缩短它。
void delete_last_element(node*& head)
{
node **curr = &head;
while (curr[0] && curr[0]->next)
curr = &curr[0]->next;
delete *curr;
*curr = nullptr;
}
在插入函数中，您始终在指向头部旁边设置：
curr->next = head;
最重要的是，您将头部更改为最新元素，
head = curr;
这是链表中的最后一项。所以你实际上是在意外地向后制作链表。
为了把它画出来，这就是你正在做的事情;向下的箭头指向头部，侧向箭头指向下一个
插入 1：
|
v
1
您将其设置为下一个是前一个头，即 1，然后您将当前节点 2 设置为新头）
|
v
1 <- 2
插入 3：
|
v
1 <- 2 <- 3
归在这里很有用。列表为：
- 空
- 只有一个元素
- 具有多个元素
我们分别处理这三种情况如下：
void delete_last_element( Node*& head ) {
if(head == NULL) {
// The list is empty, nothing to remove.
// Just do nothing and return
return;
}
else if (head->next == NULL) {
// This list has exactly one element.
// Remove it and return
delete head; // free the memory
head = NULL; // the single-element list is now an empty list
return;
}
else {
// We have a list with more than one element.
// Let's be lazy
delete_last_element(head->next);
return;
}
这三个案例中的每一种都依次处理。最后一种情况（"具有多个元素的列表"）只需调用 delete_last_element(head->next); 即可处理。这个想法是从 head 开始的 5 元素列表中删除最后一个元素与删除从 head->next 开始的 4 元素列表完全相同。