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

Question

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

这是我对节点的定义

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，因为我知道它是最后一个元素并且 return。

现在我知道第一个元素不是最后一个元素，我将 head 分配给 curr，即第二个元素。从这里我进入 while 循环并检查下一个元素（从第 3 个开始）是否为空，如果是我删除当前元素，如果不是我移动到下一个元素然后检查下一个元素。

现在我的链表最初以 3 2 1 开头，但是由于某种原因，当我运行函数 delete_last_element 时它变成了 2 而不是 3 2。

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

谢谢

Answer 1

在你的插入函数中，你总是将 next 设置为指向 head:

curr->next = head;

最重要的是你正在改变你的头到最新的元素，

head = curr;

这是链表中的最后一项。所以你实际上是不小心把链表弄反了。

把它画出来，这就是你在做的；向下的箭头指向head，侧面的箭头指向next

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

Here is a demo showing its use.

一旦你理解了上面的代码，你就可以弄清楚如何缩短它了。

void delete_last_element(node*& head)
{
    node **curr = &head;
    while (curr[0] && curr[0]->next)
        curr = &curr[0]->next;

    delete *curr;
    *curr = nullptr;
}

Answer 3

递归在这里很有用。列表是：

empty

has exactly one element

has more than one element

我们对这三种情况的处理如下：

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

三个案例依次处理。最后一种情况 ("a list that has more than one element") 只需调用 delete_last_element(head->next); 即可处理。这个想法是从 head 开始的 5 元素列表中删除最后一个元素与删除从 head->next.

开始的 4 元素列表完全相同

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

Why is my delete_last_element of a linked list deleting the first element?

c++

linked-list