从链接列表的末尾删除

Question

我正在编写一个程序，该程序生成6个随机数，并将它们放入链表中并输出。然后，在它获得所有6个数字后，它删除第一个节点并输出剩余的5个，然后它将删除最后一个节点并来回输出剩余的4个，直到没有节点为止。无论如何，我可以创建链表，在其中存储节点并输出它们，每次都可以删除第一个节点，但我不知道如何删除最后一个节点。如有任何关于如何删除最后一个节点的帮助，我们将不胜感激。我正在使用函数pop_back删除最后一个节点。。。

#include <iostream>
#include <ctime>
#include <cstdlib>
#include "SortedLinkedList.h"
using namespace std;
struct node
{
    int data;
    node *next;
};
node *head = NULL;
void push_sorted(int value)
{
    node *newNode = new node;
    newNode->data = value;
    newNode->next = NULL; 
    if(head == NULL)
    {
        head = newNode;
    }
    else
    {
        node *newNode_2 = head;
        while(newNode_2->next != NULL)
        {
            newNode_2 = newNode_2-> next;
        }
        newNode_2->next = newNode;
    }
}
void pop_front()
{
    node *temp;
    temp = head;
    head = head->next;
    free(temp);
}
void pop_back()
{
}
bool isEmpty(int count)
{
    if(count == 0)
    {
        return false;
    }
    else
    {
        return true;
    }
}
void print()
{
    node* current = head;
    while(current != NULL)
    {
        cout << current-> data << " ";
        current = current->next;
    }
    cout << endl;
}
int main()
{
    int count  = 6;
    const int NUMS = 6;     //insert elements into the sorted linked list in an ascending order
    const int RANGE = 21;   //each element is in the range [-10, 10]
    /*SortedLinkedList mylist;*/
    srand(time(0));
    for (int i = 0; i < NUMS; i++)
    {
        int data = (rand() % RANGE) - 10;
        cout << "Adding " << data << " to the sorted linked list: " << endl;
        push_sorted(data);
        print();
    }
    while ((isEmpty(count) == true))
    {
        cout << "Removing from front..." << endl;
        pop_front();
        print();
        count --;
        cout << "Removing from back..." << endl;
        pop_back();
        print();
        count --;
    }
    system("pause");
    return 0;
}

Answer 1

您已经很好地完成了MCVE的其余部分（输入、输出、插入等）。（不过，我建议您将方法移动到结构中。）

我决定提供以下递归解决方案。只需进行一次测试，它似乎可以工作。

如果您不了解递归，我建议您采用循环迭代方法。如果你确实理解了递归，你仍然应该处理循环迭代方法，无论如何，很多人都觉得它更容易。

void pop_back()
{
   bool isLast = false;
   if(nullptr != head)    // does list have any elements?
   {
      // use the recursive form to find last, and 
      // return a bool to find the next to last
      isLast = head->pop_backR();  // recurse to last element
      if (isLast) // i.e. only 1 element in list, the head
      {
         delete (head);  // remove it
         head = nullptr; 
      }
   }
   // note:  on std::list, calling pop_back when container empty is undefined.
  //    tbd - throw underflow?   your choice here
}

bool pop_backR()
{
   if(nullptr == next)
      return true; // last node found, return feedback to previous node
   // last node not found, continue search
   bool nxtIsLast = next->pop_backR();
   // check - did we find the last element yet?
   if (nxtIsLast)
   {
      // at this point we know next is last
      delete (next);   // so delete last
      next = nullptr;  // remove it from list
      return false;    // we are done, now decurse with no more deletes
   }
   else  // previous recursion did not find it
      return false; 
}

这似乎奏效了，但还没有经过很好的测试。

我的系统输出-

Adding -9 to the sorted linked list: 
-9 
Adding 0 to the sorted linked list: 
-9 0 
Adding -6 to the sorted linked list: 
-9 0 -6 
Adding 10 to the sorted linked list: 
-9 0 -6 10 
Adding -8 to the sorted linked list: 
-9 0 -6 10 -8 
Adding -3 to the sorted linked list: 
-9 0 -6 10 -8 -3 
Removing from front...
0 -6 10 -8 -3 
Removing from back...
0 -6 10 -8 
Removing from front...
-6 10 -8 
Removing from back...
-6 10 
Removing from front...
10 
Removing from back...