从链表的末尾删除

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（输入，输出，插件等）的其余很好。 （但是，我会，但是，建议您移动结构内的方法。）

我已决定提供以下递归解决方案。只有一个测试，它似乎工作。

如果你不了解递归，我建议你解决循环迭代的方法。如果你确实理解了这个rec​​usultion，那么你仍然应该解决循环迭代的方法，无论如何，这种方法很容易找到。

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...