2487. Remove Nodes From Linked List - Explanation

Description

Remove every node that has a strictly greater value somewhere after it in the singly linked list. Return the head of the remaining list, preserving the original order of the surviving nodes. An equal value to the right does not cause removal. Input and output arrays list node values from head to tail.

Example 1:

Remove Nodes From Linked List, example 1: illustration of the example

Input: head = [4,7,3,6,2]

Output: [7,6,2]

Explanation: Remove 4 because 7 is later, and remove 3 because 6 is later. The surviving nodes form 7 -> 6 -> 2.

Example 2:

Remove Nodes From Linked List, example 2: illustration of the example

Input: head = [5,5,3,3]

Output: [5,5,3,3]

Explanation: No node has a strictly greater value to its right. Equal later values do not count, so every node remains.

Example 3:

Remove Nodes From Linked List, example 3: illustration of the example

Input: head = [1,2,3,4]

Output: [4]

Explanation: Each of the first three nodes has a greater value later in the list. Only the final node, containing 4, remains.

Constraints:

The list contains between 1 and 100000 nodes.
1 <= Node.val <= 100000

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Linked List Fundamentals - Understanding singly linked list structure, traversal, and pointer manipulation
Monotonic Stack - Using a stack that maintains elements in strictly increasing or decreasing order
Linked List Reversal - Reversing a linked list in-place using iterative pointer swapping

1. Convert To Array

Intuition

A node should be removed if there exists a larger value somewhere to its right. To check this efficiently, we first convert the linked list into an array. Then we traverse the array from right to left, keeping track of the maximum value seen so far. Any node with a value smaller than this running maximum gets removed by adjusting the previous node's pointer.

Algorithm

Create an array with a dummy node at the start, followed by all nodes from the linked list.
Initialize rightMaxi to track the maximum node seen from the right.
Traverse the array from right to left:
- If the current node's value is less than rightMaxi.val, update the previous node's next pointer to skip it.
- Otherwise, update rightMaxi to the current node.
Return arr[0].next as the new head.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur, arr = head, [ListNode(0, head)]
        while cur:
            arr.append(cur)
            cur = cur.next

        rightMaxi = ListNode(0, None)
        for i in range(len(arr) - 1, 0, -1):
            if rightMaxi.val > arr[i].val:
                arr[i - 1].next = rightMaxi
            else:
                rightMaxi = arr[i]

        return arr[0].next

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class Solution {
    public ListNode removeNodes(ListNode head) {
        List<ListNode> arr = new ArrayList<>();
        arr.add(new ListNode(0, head));
        ListNode cur = head;

        while (cur != null) {
            arr.add(cur);
            cur = cur.next;
        }

        ListNode rightMaxi = new ListNode(0, null);
        for (int i = arr.size() - 1; i > 0; i--) {
            if (rightMaxi.val > arr.get(i).val) {
                arr.get(i - 1).next = rightMaxi;
            } else {
                rightMaxi = arr.get(i);
            }
        }

        return arr.get(0).next;
    }
}

/**
 * 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) {
        vector<ListNode*> arr;
        arr.push_back(new ListNode(0, head));
        ListNode* cur = head;

        while (cur) {
            arr.push_back(cur);
            cur = cur->next;
        }

        ListNode* rightMaxi = new ListNode(0, nullptr);
        for (int i = arr.size() - 1; i > 0; i--) {
            if (rightMaxi->val > arr[i]->val) {
                arr[i - 1]->next = rightMaxi;
            } else {
                rightMaxi = arr[i];
            }
        }

        return arr[0]->next;
    }
};

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     constructor(val = 0, next = null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
class Solution {
    /**
     * @param {ListNode} head
     * @return {ListNode}
     */
    removeNodes(head) {
        let cur = head,
            arr = [{ val: 0, next: head }];
        while (cur) {
            arr.push(cur);
            cur = cur.next;
        }

        let rightMaxi = { val: 0, next: null };
        for (let i = arr.length - 1; i > 0; i--) {
            if (rightMaxi.val > arr[i].val) {
                arr[i - 1].next = rightMaxi;
            } else {
                rightMaxi = arr[i];
            }
        }

        return arr[0].next;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode RemoveNodes(ListNode head) {
        var arr = new List<ListNode>();
        arr.Add(new ListNode(0, head));
        var cur = head;

        while (cur != null) {
            arr.Add(cur);
            cur = cur.next;
        }

        var rightMaxi = new ListNode(0, null);
        for (int i = arr.Count - 1; i > 0; i--) {
            if (rightMaxi.val > arr[i].val) {
                arr[i - 1].next = rightMaxi;
            } else {
                rightMaxi = arr[i];
            }
        }

        return arr[0].next;
    }
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNodes(head *ListNode) *ListNode {
    arr := []*ListNode{{Val: 0, Next: head}}
    cur := head

    for cur != nil {
        arr = append(arr, cur)
        cur = cur.Next
    }

    rightMaxi := &ListNode{Val: 0, Next: nil}
    for i := len(arr) - 1; i > 0; i-- {
        if rightMaxi.Val > arr[i].Val {
            arr[i-1].Next = rightMaxi
        } else {
            rightMaxi = arr[i]
        }
    }

    return arr[0].Next
}

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun removeNodes(head: ListNode?): ListNode? {
        val arr = mutableListOf<ListNode>()
        val dummy = ListNode(0)
        dummy.next = head
        arr.add(dummy)
        var cur = head

        while (cur != null) {
            arr.add(cur)
            cur = cur.next
        }

        var rightMaxi = ListNode(0)
        for (i in arr.size - 1 downTo 1) {
            if (rightMaxi.`val` > arr[i].`val`) {
                arr[i - 1].next = rightMaxi
            } else {
                rightMaxi = arr[i]
            }
        }

        return arr[0].next
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func removeNodes(_ head: ListNode?) -> ListNode? {
        var arr: [ListNode] = [ListNode(0, head)]
        var cur = head

        while cur != nil {
            arr.append(cur!)
            cur = cur?.next
        }

        var rightMaxi = ListNode(0, nil)
        for i in stride(from: arr.count - 1, through: 1, by: -1) {
            if rightMaxi.val > arr[i].val {
                arr[i - 1].next = rightMaxi
            } else {
                rightMaxi = arr[i]
            }
        }

        return arr[0].next
    }
}

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
impl Solution {
    pub fn remove_nodes(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut vals = Vec::new();
        let mut cur = &head;
        while let Some(node) = cur {
            vals.push(node.val);
            cur = &node.next;
        }

        let mut right_max = 0;
        let mut keep = vec![false; vals.len()];
        for i in (0..vals.len()).rev() {
            if vals[i] >= right_max {
                keep[i] = true;
                right_max = vals[i];
            }
        }

        let mut dummy = Box::new(ListNode { val: 0, next: None });
        let mut tail = &mut dummy;
        for i in 0..vals.len() {
            if keep[i] {
                tail.next = Some(Box::new(ListNode { val: vals[i], next: None }));
                tail = tail.next.as_mut().unwrap();
            }
        }
        dummy.next
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Monotonic Decreasing Stack

Intuition

We need to keep only nodes that have no larger value to their right. A monotonic decreasing stack naturally maintains this property. As we traverse the list, we pop any stack elements that are smaller than the current node's value. This ensures the stack always contains values in decreasing order from bottom to top, which are exactly the nodes that should remain.

Algorithm

Initialize an empty stack to store node values.
Traverse the linked list:
- While the stack is not empty and the current value is greater than the top of the stack, pop from the stack.
- Push the current value onto the stack.
Build a new linked list from the stack values in order.
Return the head of the new list.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        stack = []
        cur = head

        while cur:
            while stack and cur.val > stack[-1]:
                stack.pop()
            stack.append(cur.val)
            cur = cur.next

        dummy = ListNode()
        cur = dummy

        for num in stack:
            cur.next = ListNode(num)
            cur = cur.next

        return dummy.next

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class Solution {
    public ListNode removeNodes(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        ListNode cur = head;

        while (cur != null) {
            while (!stack.isEmpty() && cur.val > stack.peek()) {
                stack.pop();
            }
            stack.push(cur.val);
            cur = cur.next;
        }

        ListNode dummy = new ListNode();
        cur = dummy;

        for (int num : stack) {
            cur.next = new ListNode(num);
            cur = cur.next;
        }

        return dummy.next;
    }
}

/**
 * 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) {
        vector<int> stack;
        ListNode* cur = head;

        while (cur) {
            while (!stack.empty() && cur->val > stack.back()) {
                stack.pop_back();
            }
            stack.push_back(cur->val);
            cur = cur->next;
        }

        ListNode* dummy = new ListNode();
        cur = dummy;

        for (int num : stack) {
            cur->next = new ListNode(num);
            cur = cur->next;
        }

        return dummy->next;
    }
};

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     constructor(val = 0, next = null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
class Solution {
    /**
     * @param {ListNode} head
     * @return {ListNode}
     */
    removeNodes(head) {
        let stack = [];
        let cur = head;

        while (cur) {
            while (stack.length && cur.val > stack[stack.length - 1]) {
                stack.pop();
            }
            stack.push(cur.val);
            cur = cur.next;
        }

        let dummy = new ListNode();
        cur = dummy;

        for (let num of stack) {
            cur.next = new ListNode(num);
            cur = cur.next;
        }

        return dummy.next;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode RemoveNodes(ListNode head) {
        var stack = new List<int>();
        var cur = head;

        while (cur != null) {
            while (stack.Count > 0 && cur.val > stack[stack.Count - 1]) {
                stack.RemoveAt(stack.Count - 1);
            }
            stack.Add(cur.val);
            cur = cur.next;
        }

        var dummy = new ListNode();
        cur = dummy;

        foreach (int num in stack) {
            cur.next = new ListNode(num);
            cur = cur.next;
        }

        return dummy.next;
    }
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNodes(head *ListNode) *ListNode {
    stack := []int{}
    cur := head

    for cur != nil {
        for len(stack) > 0 && cur.Val > stack[len(stack)-1] {
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, cur.Val)
        cur = cur.Next
    }

    dummy := &ListNode{}
    cur = dummy

    for _, num := range stack {
        cur.Next = &ListNode{Val: num}
        cur = cur.Next
    }

    return dummy.Next
}

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun removeNodes(head: ListNode?): ListNode? {
        val stack = mutableListOf<Int>()
        var cur = head

        while (cur != null) {
            while (stack.isNotEmpty() && cur.`val` > stack.last()) {
                stack.removeAt(stack.size - 1)
            }
            stack.add(cur.`val`)
            cur = cur.next
        }

        val dummy = ListNode(0)
        var node: ListNode? = dummy

        for (num in stack) {
            node?.next = ListNode(num)
            node = node?.next
        }

        return dummy.next
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func removeNodes(_ head: ListNode?) -> ListNode? {
        var stack = [Int]()
        var cur = head

        while cur != nil {
            while !stack.isEmpty && cur!.val > stack.last! {
                stack.removeLast()
            }
            stack.append(cur!.val)
            cur = cur?.next
        }

        let dummy = ListNode()
        var node: ListNode? = dummy

        for num in stack {
            node?.next = ListNode(num)
            node = node?.next
        }

        return dummy.next
    }
}

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
impl Solution {
    pub fn remove_nodes(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut stack: Vec<i32> = Vec::new();
        let mut cur = &head;

        while let Some(node) = cur {
            while let Some(&top) = stack.last() {
                if node.val > top {
                    stack.pop();
                } else {
                    break;
                }
            }
            stack.push(node.val);
            cur = &node.next;
        }

        let mut dummy = Box::new(ListNode { val: 0, next: None });
        let mut tail = &mut dummy;
        for num in stack {
            tail.next = Some(Box::new(ListNode { val: num, next: None }));
            tail = tail.next.as_mut().unwrap();
        }
        dummy.next
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Recursion

Intuition

Recursion lets us process the list from right to left naturally. We first recurse to the end, then on the way back, each node compares itself to whatever remains in the processed suffix. If the next node has a larger value, the current node should be removed, so we return head.next instead. Otherwise, we keep the current node.

Algorithm

Base case: if head is null, return null.
Recursively process head.next and assign the result back to head.next.
If head.next exists and head.val < head.next.val, return head.next (remove current node).
Otherwise, return head (keep current node).

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None

        head.next = self.removeNodes(head.next)
        if head.next and head.val < head.next.val:
            return head.next
        return head

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class Solution {
    public ListNode removeNodes(ListNode head) {
        if (head == null) return null;

        head.next = removeNodes(head.next);
        if (head.next != null && head.val < head.next.val) {
            return head.next;
        }
        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) {
        if (!head) return nullptr;

        head->next = removeNodes(head->next);
        if (head->next && head->val < head->next->val) {
            return head->next;
        }
        return head;
    }
};

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     constructor(val = 0, next = null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
class Solution {
    /**
     * @param {ListNode} head
     * @return {ListNode}
     */
    removeNodes(head) {
        if (!head) return null;

        head.next = this.removeNodes(head.next);
        if (head.next && head.val < head.next.val) {
            return head.next;
        }
        return head;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode RemoveNodes(ListNode head) {
        if (head == null) return null;

        head.next = RemoveNodes(head.next);
        if (head.next != null && head.val < head.next.val) {
            return head.next;
        }
        return head;
    }
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNodes(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }

    head.Next = removeNodes(head.Next)
    if head.Next != nil && head.Val < head.Next.Val {
        return head.Next
    }
    return head
}

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun removeNodes(head: ListNode?): ListNode? {
        if (head == null) return null

        head.next = removeNodes(head.next)
        if (head.next != null && head.`val` < head.next!!.`val`) {
            return head.next
        }
        return head
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func removeNodes(_ head: ListNode?) -> ListNode? {
        guard let head = head else { return nil }

        head.next = removeNodes(head.next)
        if let next = head.next, head.val < next.val {
            return head.next
        }
        return head
    }
}

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
impl Solution {
    pub fn remove_nodes(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        if head.is_none() {
            return None;
        }
        let mut node = head.unwrap();
        node.next = Self::remove_nodes(node.next);
        if let Some(ref next) = node.next {
            if node.val < next.val {
                return node.next;
            }
        }
        Some(node)
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$ for recursion stack.

4. Reverse Twice

Intuition

Finding the maximum to the right is hard when traversing left to right, but finding the maximum to the left is easy. By reversing the list first, the problem transforms: now we just need to keep nodes that are greater than or equal to all previous nodes. We traverse once while tracking the running maximum and remove smaller nodes. Finally, we reverse again to restore the original order.

Algorithm

Reverse the linked list.
Traverse the reversed list, tracking the maximum value seen so far (cur_max):
- If cur.next.val < cur_max, skip it by setting cur.next = cur.next.next.
- Otherwise, update cur_max and move to the next node.
Reverse the list again to restore original order.
Return the new head.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def reverse(head):
            prev, cur = None, head
            while cur:
                tmp = cur.next
                cur.next = prev
                prev, cur = cur, tmp
            return prev

        head = reverse(head)
        cur = head
        cur_max = head.val

        while cur and cur.next:
            if cur.next.val < cur_max:
                cur.next = cur.next.next
            else:
                cur_max = cur.next.val
                cur = cur.next

        return reverse(head)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class Solution {
    public ListNode removeNodes(ListNode head) {
        head = reverse(head);
        ListNode cur = head;
        int curMax = head.val;

        while (cur != null && cur.next != null) {
            if (cur.next.val < curMax) {
                cur.next = cur.next.next;
            } else {
                curMax = cur.next.val;
                cur = cur.next;
            }
        }
        return reverse(head);
    }

    private ListNode reverse(ListNode head) {
        ListNode prev = null, cur = head;
        while (cur != null) {
            ListNode tmp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = tmp;
        }
        return prev;
    }
}

/**
 * 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* reverse(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* cur = head;
        while (cur) {
            ListNode* tmp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = tmp;
        }
        return prev;
    }

    ListNode* removeNodes(ListNode* head) {
        head = reverse(head);
        ListNode* cur = head;
        int cur_max = head->val;

        while (cur && cur->next) {
            if (cur->next->val < cur_max) {
                cur->next = cur->next->next;
            } else {
                cur_max = cur->next->val;
                cur = cur->next;
            }
        }
        return reverse(head);
    }
};

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     constructor(val = 0, next = null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
class Solution {
    /**
     * @param {ListNode} head
     * @return {ListNode}
     */
    removeNodes(head) {
        const reverse = (head) => {
            let prev = null,
                cur = head;
            while (cur) {
                let tmp = cur.next;
                cur.next = prev;
                prev = cur;
                cur = tmp;
            }
            return prev;
        };

        head = reverse(head);
        let cur = head;
        let cur_max = head.val;

        while (cur && cur.next) {
            if (cur.next.val < cur_max) {
                cur.next = cur.next.next;
            } else {
                cur_max = cur.next.val;
                cur = cur.next;
            }
        }
        return reverse(head);
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    private ListNode Reverse(ListNode head) {
        ListNode prev = null, cur = head;
        while (cur != null) {
            ListNode tmp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = tmp;
        }
        return prev;
    }

    public ListNode RemoveNodes(ListNode head) {
        head = Reverse(head);
        ListNode cur = head;
        int curMax = head.val;

        while (cur != null && cur.next != null) {
            if (cur.next.val < curMax) {
                cur.next = cur.next.next;
            } else {
                curMax = cur.next.val;
                cur = cur.next;
            }
        }
        return Reverse(head);
    }
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNodes(head *ListNode) *ListNode {
    reverse := func(head *ListNode) *ListNode {
        var prev *ListNode = nil
        cur := head
        for cur != nil {
            tmp := cur.Next
            cur.Next = prev
            prev = cur
            cur = tmp
        }
        return prev
    }

    head = reverse(head)
    cur := head
    curMax := head.Val

    for cur != nil && cur.Next != nil {
        if cur.Next.Val < curMax {
            cur.Next = cur.Next.Next
        } else {
            curMax = cur.Next.Val
            cur = cur.Next
        }
    }
    return reverse(head)
}

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    private fun reverse(head: ListNode?): ListNode? {
        var prev: ListNode? = null
        var cur = head
        while (cur != null) {
            val tmp = cur.next
            cur.next = prev
            prev = cur
            cur = tmp
        }
        return prev
    }

    fun removeNodes(head: ListNode?): ListNode? {
        var h = reverse(head)
        var cur = h
        var curMax = h!!.`val`

        while (cur != null && cur.next != null) {
            if (cur.next!!.`val` < curMax) {
                cur.next = cur.next!!.next
            } else {
                curMax = cur.next!!.`val`
                cur = cur.next
            }
        }
        return reverse(h)
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func reverse(_ head: ListNode?) -> ListNode? {
        var prev: ListNode? = nil
        var cur = head
        while cur != nil {
            let tmp = cur?.next
            cur?.next = prev
            prev = cur
            cur = tmp
        }
        return prev
    }

    func removeNodes(_ head: ListNode?) -> ListNode? {
        var head = reverse(head)
        var cur = head
        var curMax = head!.val

        while cur != nil && cur?.next != nil {
            if cur!.next!.val < curMax {
                cur?.next = cur?.next?.next
            } else {
                curMax = cur!.next!.val
                cur = cur?.next
            }
        }
        return reverse(head)
    }
}

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
impl Solution {
    pub fn remove_nodes(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        fn reverse(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
            let mut prev: Option<Box<ListNode>> = None;
            let mut cur = head;
            while let Some(mut node) = cur {
                cur = node.next.take();
                node.next = prev;
                prev = Some(node);
            }
            prev
        }

        let mut head = reverse(head);
        let cur_max;
        {
            let h = head.as_ref().unwrap();
            cur_max = h.val;
        }
        let mut cur_max = cur_max;
        let mut cur = &mut head;
        while cur.is_some() && cur.as_ref().unwrap().next.is_some() {
            let next_val = cur.as_ref().unwrap().next.as_ref().unwrap().val;
            if next_val < cur_max {
                let next_next = cur.as_mut().unwrap().next.as_mut().unwrap().next.take();
                cur.as_mut().unwrap().next = next_next;
            } else {
                cur_max = next_val;
                cur = &mut cur.as_mut().unwrap().next;
            }
        }
        reverse(head)
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

Common Pitfalls

Comparing with Immediate Neighbor Instead of Maximum

The problem requires removing nodes that have any larger value to their right, not just an immediately adjacent larger value. A node should be kept only if it is greater than or equal to all nodes to its right. Using the wrong comparison leads to incorrect removals.

Incorrect Stack Maintenance

When using a monotonic stack, the stack must remain strictly decreasing. Forgetting to pop smaller elements before pushing, or using the wrong comparison operator (e.g., >= instead of >), breaks the invariant and produces wrong results.

Losing the New Head After Reversal

In the reverse-twice approach, both reversals change which node is the head. Failing to capture and return the correct head after the second reversal causes the function to return a pointer into the middle of the list or a stale reference.