Удалить все последние узлы связанного списка, которые имеют значение = 0

Question

У меня есть список связанных ссылок: 1 0 1 2 0 0 0. Я хочу удалить весь последний узел «0», чтобы мой список выглядел так: 1 0 1 2. Я попытался с помощью рекурсии:

Node *trimtList(Node* head) { 
    if (head->next->data == 0 && head->next->next == NULL) { 
     head->next = NULL; 
     return head; 
    } 
    trimList(head->next); 
    return head; 
} 

Я понимаю, что этот метод просто удалить последнюю 0, не все последние 0 ...

Node *trimtList(Node* head) { 
    if (head && !trimtList(head->next) && head->data == 0) { 
     delete head; 
     head = nullptr; 
    } 
    return head; 
} 

int main() { 
    List a; 
    a.head= new Node(1); 
    a.head->next = new Node(0); 
    a.head->next->next = new Node(2); 
    a.head->next->next->next = new Node(0); 
    a.head->next->next->next->next = new Node(0); 
    a.head= trimtList(a.head); 
    cout << a << endl; 
} 

Выход 1 0 2 2, а затем окно уже перестает работать ...

Answer 1

Это должно быть что-то вроде:

Node *trimList(Node* head) { 
    if (trimList(head->next).next == NULL && head->next->data == 0) { 
     head->next = NULL; 
    } 

    return head; 
} 

Вызывая trimList в начале, а не в конце, мы убеждаемся, что впереди нас лежит не более одного узла.

Answer 2

Вот мои пять центов. :)

#include <iostream> 

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

void push_front(Node * &head, int data) 
{ 
    Node *tmp = new Node { data, head }; 
    head = tmp; 
} 

std::ostream & display(Node * &head, std::ostream &os = std::cout) 
{ 
    for (Node *tmp = head; tmp; tmp = tmp->next) 
    { 
     os << tmp->data << ' '; 
    } 

    return os; 
}  

Node * rtrim(Node * &head, int data = 0) 
{ 
    if (head && !rtrim(head->next, data) && head->data == data) 
    { 
     delete head; 
     head = nullptr; 
    } 

    return head; 
} 

int main() 
{ 
    Node *head = nullptr; 

    for (int x : { 0, 0, 0, 2, 1, 0, 1 }) push_front(head, x); 
    display(head) << std::endl; 

    rtrim(head); 
    display(head) << std::endl; 

    rtrim(head, 2); 
    display(head) << std::endl; 

    rtrim(head, 1); 
    display(head) << std::endl; 

    rtrim(head); 
    display(head) << std::endl; 

    rtrim(head, 1); 
    display(head) << std::endl; 
}  

Выход программы

1 0 1 2 0 0 0 
1 0 1 2 
1 0 1 
1 0 
1 

Коротко говоря собственную функцию может выглядеть

Node *trimtList(Node* head) { 
    if (head && !trimList(head->next) && head->data == 0) { 
     delete head; 
     head = nullptr; 
    } 

    return head; 
} 

и должен называться как

head = trimtList(head);