为什么链表的delete_last_element要删除第一个元素？

Question

我正在编写一个函数，该函数应该删除链表的最后一个元素

这是我对节点的定义

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

我有一个节点列表1，它为值1、2、3运行了3次insert函数

insert函数如下所示

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循环，检查下一个元素（从第3个开始）是否为空，如果是，我删除当前元素，如果不是，我移动head到下一个元素，然后检查之后的下一个元素。

现在，我的链表最初是以3 2 1开始的，但无论出于什么原因，当我运行delete_last_element函数时，它变成了2而不是3 2。

谁能告诉我我可能做错了什么？

谢谢

Answer 1

在insert函数中，您总是将next设置为point to head：

curr->next = head;

最重要的是，你把头换成了最新的元素，

head = curr;

它是链表中的最后一项。所以你实际上是，不小心把链表倒过来了。

把它画出来，这就是你正在做的；向下的箭头指向头部，侧向的箭头指向下一个

插入1：

|
v
1

插入2：（您正在创建一个新节点:2，然后将其设置为上一个头，即1，然后将当前节点2设置为新头）

     |
     v
1 <- 2

插入3：

          | 
          v
1 <- 2 <- 3

Answer 2

基本上，在本例中需要注意两个条件：

• 列表为空。
• 列表中只有一个元素。

如果列表为空，则由指向nullptr的head指针来指示。如果没有列表，那么就没有要删除的内容，所以我们可以退出函数：

if (head == nullptr)
    return;

检查列表中是否只有一个元素是有用的原因是，如果我们保留两个指针来遍历列表--一个指向当前元素，一个在当前元素之前。删除当前节点后，“Previous”指针必须将其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;
}