2487.从链表中移除节点

链接：2487.从链表中移除节点
难度：Medium
标签：栈、递归、链表、单调栈
简介：给你一个链表的头节点 head 。对于列表中的每个节点 node ，如果其右侧存在一个具有 严格更大 值的节点，则移除 node 。返回修改后链表的头节点 head 。

题解 1 - cpp

• 编辑时间：2022-11-27
• 执行用时：356ms
• 内存消耗：157.1MB
• 编程语言：cpp
• 解法介绍：递归，记录后面的最大值。

# define X first
# define Y second
# define lb(x) ((x) & (-x))
# define mem(a,b) memset(a,b,sizeof(a))
# define debug freopen("r.txt","r",stdin)
# define pi pair<int,int>
using namespace std;
typedef long long ll;
class Solution {
public:
    ListNode* removeNodes(ListNode* head) {
      int maxnum = 0;
      return _removeNodes(head, maxnum);
    }
    ListNode* _removeNodes(ListNode *head, int &maxnum) {
      if (head == nullptr) return nullptr;
      ListNode *next = _removeNodes(head->next, maxnum);
      if (head->val >= maxnum) {
        head->next = next;
        next = head;
      }
      maxnum = max(maxnum, head->val);
      return next;
    }
};

题解 2 - python

• 编辑时间：2024-01-03
• 执行用时：644ms
• 内存消耗：55.98MB
• 编程语言：python
• 解法介绍：单调栈记录最大序列，遍历时记录父节点。

class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        p = tempHead = ListNode(0, head)
        s = []
        map = {}
        while p.next:
            map[p.next] = p 
            while s and s[-1].val < p.next.val:
                node = s.pop()
                parent = map[node]
                parent.next = node.next
                map[node.next] = parent
            s.append(p.next)
            p = p.next
        return tempHead.next

题解 3 - python

• 编辑时间：2024-01-03
• 执行用时：360ms
• 内存消耗：59.6MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        self.max = 0
        def dfs(node: Optional[ListNode]) -> Optional[ListNode]:
            if not node: return node
            node.next = dfs(node.next)
            if self.max > node.val: return node.next
            self.max = node.val
            return node
        return dfs(head)

题解 4 - rust

• 编辑时间：2024-01-03
• 执行用时：72ms
• 内存消耗：11.33MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn remove_nodes(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut max = 0;
        fn dfs(node: Option<Box<ListNode>>, max: &mut i32) -> Option<Box<ListNode>> {
            match node {
                None => None,
                Some(mut node) => {
                    node.next = dfs(node.next.take(), max);
                    if *max > node.val {
                        node.next.take()
                    } else {
                        *max = node.val;
                        Some(node)
                    }
                }
            }
        }
        dfs(head, &mut max)
    }
}