LeetCode 每日一题 Day 32 ||递归&单调栈

2487. 从链表中移除节点

给你一个链表的头节点 head 。

移除每个右侧有一个更大数值的节点。

返回修改后链表的头节点 head 。

示例 1：

输入：head = [5,2,13,3,8]
输出：[13,8]
解释：需要移除的节点是 5 ，2 和 3 。

• 节点 13 在节点 5 右侧。
• 节点 13 在节点 2 右侧。
• 节点 8 在节点 3 右侧。

示例 2：

输入：head = [1,1,1,1]
输出：[1,1,1,1]
解释：每个节点的值都是 1 ，所以没有需要移除的节点。

提示：

给定列表中的节点数目在范围 [1, 105] 内
1 <= Node.val <= 1e5

既然题目要倒着看最大值，明显可以用到递归,利用递归确定每个数右侧都是比他大的：

/**
 * 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) {
        if(head -> next == nullptr) {
            return head;
        }
        ListNode* node = removeNodes(head -> next);
        if(node -> val > head -> val) {
            return node;
        }
        head -> next = node;
        return head;
    }
};

看完题解后还有另外的解法，也就是单调栈：

/**
 * 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) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* cur = head;
        vector<ListNode*> stk;
        for (ListNode* cur = head; cur; cur = cur->next) {
            while (stk.size() && stk.back()->val < cur->val) {
                stk.pop_back();
            }
            if (stk.size()) {
                stk.back()->next = cur;
            } else {
                dummy->next = cur;
            }
            stk.push_back(cur);
        }
        return dummy->next;
    }
};

灵神题解中还用了迭代来做：

class Solution {
    ListNode *reverseList(ListNode *head) {
        ListNode *pre = nullptr, *cur = head;
        while (cur) {
            ListNode *nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
public:
    ListNode *removeNodes(ListNode *head) {
        head = reverseList(head);
        ListNode *cur = head;
        while (cur->next) {
            if (cur->val > cur->next->val) {
                cur->next = cur->next->next;
            } else {
                cur = cur->next;
            }
        }
        return reverseList(head);
    }
};