Remove Nodes From Linked List Solution

Problem

Given a linked list, remove every node that has a node with a strictly greater value somewhere to its right. A node survives only if it is at least as large as every node that comes after it.

→

→∅

[5,2,13,3,8]

Input: head = [5, 2, 13, 3, 8]
Output: [13, 8]
Explanation: 5 and 2 are removed because 13 comes after them; 3 is removed because 8 comes after it.

Counter-example: [1, 1, 1] → [1, 1, 1]. Equal values do not trigger removal — only a strictly greater value to the right causes a node to be removed.

Intuition

A node survives if and only if it is greater than or equal to every node to its right. The challenge is that we need to look forward in the list to make a decision about the current node, which is awkward for a standard left-to-right traversal. Two approaches flip this: recursion naturally processes the right side before the left, and reversing the list lets us scan right-to-left while tracking a running maximum.

Approach 1 — Recursion

Process the rest of the list first. Once the right sublist is fixed, check if the current node is dominated by the head of that fixed list. If so, skip the current node.

Base case: if head is null, return null.
Recursively fix the rest of the list: head.next = removeNodes(head.next).
After the recursive call returns, head.next is already the largest node reachable from the right.
If head.next exists and its value exceeds the current node's value, skip the current node by returning head.next.
Otherwise, keep the current node and return it.

1def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
2    if not head:
3        return None
4    
5    # fix the right side first, then evaluate the current node
6    head.next = self.removeNodes(head.next)
7    
8    if head.next and head.next.val > head.val:
9        return head.next  # current node is dominated; skip it
10    return head

Time: O(n) — each node is visited exactly once on the way down the call stack.

Space: O(n) — the recursion stack grows one frame per node.

Approach 2 — Reverse + Monotonic Filter

Reverse the list so that what was originally to the right is now to the left. Then scan left-to-right tracking the maximum value seen so far: any node smaller than the running maximum would have been dominated in the original order, so remove it. Reverse back.

Reverse the linked list in-place.
Initialize running_max to the head's value (the original tail).
Walk forward: if the next node's value is less than running_max, skip it; otherwise update running_max and advance.
Reverse the filtered list back to restore original order.

1def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
2    def reverse_list(node: Optional[ListNode]) -> Optional[ListNode]:
3        prev = None
4        curr = node
5        while curr:
6            next_node = curr.next
7            curr.next = prev
8            prev = curr
9            curr = next_node
10        return prev
11    
12    head = reverse_list(head)
13    
14    running_max = head.val  # initialize from actual head to handle negative values
15    current = head
16    while current.next:
17        if current.next.val < running_max:
18            current.next = current.next.next  # node was dominated in original order
19        else:
20            running_max = current.next.val
21            current = current.next
22    
23    return reverse_list(head)

Time: O(n) — two reversal passes and one filter pass, each O(n).

Space: O(1) — all operations are in-place with only a few pointer variables.

Complexity Summary

Approach	Time	Space	When to use
Recursion	O(n)	O(n)	Cleaner code when stack depth isn't a concern (lists up to ~10k nodes)
Reverse + Filter	O(n)	O(1)	Preferred for very long lists where call-stack overflow is a risk

Common Mistakes

Bottom-up vs top-down recursion: The recursive fix must happen on head.next before the comparison — calling removeNodes on the already-modified head.next is what makes the comparison valid. Doing the comparison first produces wrong answers.
Equal values trigger removal: Only a strictly greater value to the right removes a node. A node equal to all future nodes should stay. Using >= in the comparison instead of > incorrectly removes ties.
Initializing running max to 0: If node values can be negative (valid per constraints), initializing running_max = 0 instead of head.val will incorrectly remove all negative-valued nodes at the start of the reversed list.
Overwriting next before saving it during reversal: In the iterative reverse, curr.next = prev must happen after next_node = curr.next — otherwise the forward reference is lost.
Reversing the wrong list: The second reversal should operate on the filtered list (the result of the filter pass), not the pre-filter reversed list saved separately.

Remove Nodes From Linked List — Solution