Remove nodes from linked list

Linked List Stack Recursion Monotonic Stack

74.8% acceptance

Feb 25, 2026

2401

You are given the head of a linked list. Remove every node which has a node with a greater value anywhere to the right side of it. Return the head of the modified linked list.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn remove_nodes(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    // Collect values
    let mut vals = Vec::new();
    let mut cur = &head;
    while let Some(node) = cur {
      vals.push(node.val);
      cur = &node.next;
    }
    // Monotonic decreasing stack (keep nodes where nothing larger is to the right)
    let mut stack: Vec<i32> = Vec::new();
    for v in vals {
      while stack.last().map_or(false, |&top| top < v) {
        stack.pop();
      }
      stack.push(v);
    }
    // Reconstruct linked list
    let mut head: Option<Box<ListNode>> = None;
    for &v in stack.iter().rev() {
      let mut node = Box::new(ListNode::new(v));
      node.next = head;
      head = Some(node);
    }
    head
  }
}