LC 2487. 从链表中移除节点

发布时间:2024年01月03日

2487. 从链表中移除节点

难度: 中等

题目大意:

给你一个链表的头节点 head

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

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

img

输入:head = [5,2,13,3,8]
输出:[13,8]
解释:需要移除的节点是 5 ,2 和 3 。
- 节点 13 在节点 5 右侧。
- 节点 13 在节点 2 右侧。
- 节点 8 在节点 3 右侧。

递归

我们可以从右往左边考虑,维护一个最大值mx,如果递归到当前节点的值大于mx,那么更新最大值,同时更新指向

代码实现

class Solution {
public:
    ListNode* removeNodes(ListNode* head) {
        ListNode* res(0);
        int mx = 0;
        function<void(ListNode*)> dfs = [&](ListNode* u) -> void {
            if (!u) return;
            dfs(u->next);
            if (u->val >= mx) {
                mx = u->val;
                ListNode* t = new ListNode(mx);
                t->next = res;
                res = t;
            }
        };
        dfs(head);
        return res;
    }
};

时间复杂度: O ( n ) O(n) O(n)

单调栈

我们仔细分析题目可以发现,根据单调栈的实现过程,留下来的这些节点不就是单调栈剩余的节点吗。所以就有了下面的代码实现

代码实现

class Solution {
public:
    ListNode* removeNodes(ListNode* head) {
        stack<ListNode*> stk;
        while (head) {
            while (stk.size() && stk.top()->val < head->val) stk.pop();
            stk.push(head);
            head = head->next;
        }
        ListNode* t(0), *res;
        res = stk.top(); stk.pop();
        while (stk.size()){
            t = stk.top(); stk.pop();
            t->next = res;
            res = t;
        }
        return res;
    }
};

时间复杂度 O ( n ) O(n) O(n)

结束了

文章来源:https://blog.csdn.net/qq_74040620/article/details/135367480
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。