2487. Remove Nodes From Linked List

---

My Solution

The Key Idea for Solving This Coding Question

C++ Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode *removeNodes(ListNode *head) {
        stack<ListNode *> st;
        for (ListNode *it = head; it != nullptr; it = it->next) {
            while (!st.empty() && st.top()->val < it->val) {
                ListNode *x = st.top();
                st.pop();
                delete x;
            }
            st.push(it);
        }

        ListNode *dummy = new ListNode(), *curr = dummy;
        while (!st.empty()) {
            st.top()->next = nullptr;
            curr->next = st.top();
            curr = curr->next;
            st.pop();
        }
        curr = dummy->next;
        delete dummy;

        // Reverse the linked list.
        ListNode *newHead = nullptr;
        while (curr != nullptr) {
            ListNode *x = curr->next;
            curr->next = newHead;
            newHead = curr;
            curr = x;
        }

        return newHead;
    }
};

Time Complexity

Space Complexity

Miscellane