從鏈表的末尾刪除

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