# Remove Nodes From Linked List
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/remove-nodes-from-linked-list)
Canonical: https://scaleengineer.com/dsa/problems/remove-nodes-from-linked-list
**Patterns:** [Recursion](https://scaleengineer.com/dsa/patterns/recursion)
**Data structures:** Linked List, Stack, Monotonic Stack
---
## Problem
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._

**Example 1:**

![](https://assets.glich.co/dsa/remove-nodes-from-linked-list/image0.png) 

**Input:** head = [5,2,13,3,8]
**Output:** [13,8]
**Explanation:** The nodes that should be removed are 5, 2 and 3.
- Node 13 is to the right of node 5.
- Node 13 is to the right of node 2.
- Node 8 is to the right of node 3.

**Example 2:**

**Input:** head = [1,1,1,1]
**Output:** [1,1,1,1]
**Explanation:** Every node has value 1, so no nodes are removed.

**Constraints:**

* The number of the nodes in the given list is in the range `[1, 105]`.
* `1 <= Node.val <= 105`

# Approaches
## Brute Force with Nested Loops
This approach uses a straightforward, brute-force method. It iterates through each node of the linked list, and for each node, it performs a second scan through all the subsequent nodes to check if there exists any node with a strictly greater value. If a greater value is found, the current node is removed from the list.
**Time:** O(N^2) - For each node in the list (N nodes), we may traverse the rest of the list (up to N-1 nodes). This results in a nested loop structure, giving a quadratic time complexity. · **Space:** O(1) - We only use a constant number of extra pointers (`dummy`, `prev`, `current`, `runner`) regardless of the list size.
**Pros:** The logic is simple and easy to understand.; It operates in-place and uses O(1) extra space.
**Cons:** The time complexity of O(N^2) is highly inefficient and will likely result in a 'Time Limit Exceeded' error for large inputs as specified in the constraints (N up to 10^5).
### Explanation
The core idea is to check the removal condition for each node one by one. We can use a `dummy` head to make the removal of the first node easier. We iterate through the list with a `current` pointer. For each `current` node, we use a `runner` pointer to scan the rest of the list to its right. If the `runner` finds any node with a value greater than `current.val`, we know `current` must be removed. To remove it, we need a pointer to the node *before* `current`, let's call it `prev`. We update `prev.next` to `current.next`. If the entire scan to the right of `current` completes without finding a greater node, we keep `current` and simply advance `prev` to `current`. This nested loop structure leads to a quadratic time complexity.

```java
/**
 * 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; }
 * }
 */
class Solution {
    public ListNode removeNodes(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode current = head;
        ListNode prev = dummy;

        while (current != null) {
            boolean foundGreater = false;
            ListNode runner = current.next;
            while (runner != null) {
                if (runner.val > current.val) {
                    foundGreater = true;
                    break;
                }
                runner = runner.next;
            }

            if (foundGreater) {
                // Remove current node by linking prev to current's next
                prev.next = current.next;
            } else {
                // Keep current node, so update prev
                prev = current;
            }
            // Move to the next node in the original list
            current = current.next;
        }
        return dummy.next;
    }
}
```
### Algorithm
*   Create a `dummy` node that points to the `head` to simplify edge cases like removing the original head.
*   Use two pointers, `prev` and `current`. `prev` will point to the last node that was kept, and `current` will iterate through the list.
*   For each `current` node, start another pointer `runner` from `current.next`.
*   Iterate with `runner` through the rest of the list. If any `runner.val > current.val`, it means `current` must be removed.
*   If `current` needs to be removed, update `prev.next` to point to `current.next`, effectively skipping `current`.
*   If `current` does not need to be removed (i.e., the inner loop finishes without finding a greater value), then `current` is a valid node in the final list, so we update `prev` to `current`.
*   Advance `current` to the next node in the list and repeat the process.
*   Finally, return `dummy.next` which points to the head of the modified list.

## Recursive Approach
A more efficient approach uses recursion. The nature of the problem—where a node's fate depends on the nodes to its right—lends itself well to a post-order traversal pattern, which can be elegantly implemented with recursion. We process the list from the end to the beginning. The recursive function modifies the sublist starting from the end and returns the head of the modified sublist.
**Time:** O(N) - Each node in the linked list is visited exactly once during the recursion. · **Space:** O(N) - The space is consumed by the recursion call stack. In the worst case (a skewed list), the recursion depth can be N.
**Pros:** The code is very concise and elegant.; Achieves a linear time complexity of O(N).
**Cons:** Uses O(N) space for the recursion call stack, which can lead to a `StackOverflowError` for very long lists (e.g., N = 10^5).; Function call overhead can make it slightly slower in practice than an equivalent iterative solution.
### Explanation
The function `removeNodes(head)` will solve the problem for the list starting at `head`. The key insight is to first solve the problem for the rest of the list, `head.next`. The recursive call `removeNodes(head.next)` returns a `nextNode` which is the head of the already-processed remainder of the list. Now, we only need to decide the fate of the current `head`. The `head` should be removed if its value is less than the value of `nextNode` (since `nextNode` is a node to its right). If `head` is kept, its `next` pointer should point to `nextNode`. This post-order processing ensures that when we decide about `head`, the list to its right has already been correctly filtered.

```java
/**
 * 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; }
 * }
 */
class Solution {
    public ListNode removeNodes(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode nextNode = removeNodes(head.next);
        if (head.val < nextNode.val) {
            // The current node should be removed.
            // Return the head of the modified rest of the list.
            return nextNode;
        } else {
            // The current node should be kept.
            // Link it to the modified rest of the list.
            head.next = nextNode;
            return head;
        }
    }
}
```
### Algorithm
*   Define a recursive function that takes the `head` of a list (or sublist) as input.
*   **Base Case:** If the `head` is `null` or `head.next` is `null`, it means we are at the end of the list. No node can be to its right, so we return the `head` itself.
*   **Recursive Step:** Make a recursive call for the rest of the list: `removeNodes(head.next)`. This call will return the head of the processed sublist that follows the current `head`.
*   Let the returned node be `nextNode`. This `nextNode` is the first node in the valid, modified remainder of the list.
*   Compare the current `head.val` with `nextNode.val`. Since `nextNode` is the head of the modified sublist, all nodes that were smaller than it have already been removed. Thus, `nextNode` holds the largest value at the start of the sublist.
*   If `head.val < nextNode.val`, the current `head` must be removed. We do this by returning `nextNode` from the current function call, effectively bypassing `head`.
*   If `head.val >= nextNode.val`, the current `head` should be kept. We link it to the modified rest of the list by setting `head.next = nextNode` and return `head`.
*   The initial call to `removeNodes(head)` will return the head of the final, fully modified list.

## Monotonic Stack
This approach is an iterative equivalent of the recursive solution, using a monotonic stack. We traverse the list from left to right. A stack is used to maintain a sequence of nodes whose values are monotonically decreasing. When we encounter a new node, we pop all nodes from the stack that have a smaller value than the new node, because the new node is a 'greater value to their right'.
**Time:** O(N) - Each node is pushed onto the stack once and popped at most once. The list traversal and stack reconstruction are both linear operations. · **Space:** O(N) - In the worst-case scenario (a list with strictly decreasing values like `[5, 4, 3, 2, 1]`), all nodes will be pushed onto the stack.
**Pros:** Efficient O(N) time complexity.; Being iterative, it avoids the risk of stack overflow that a recursive solution might face with very long lists.
**Cons:** Requires O(N) extra space to store the nodes in the stack.
### Explanation
By using a stack, we can efficiently find the next greater element for a sequence of nodes. As we traverse the list, we maintain a stack of nodes that are potential candidates for the final list. When we encounter a `current` node, we compare it with the node at the top of the stack. If `current.val` is greater, it means the node on the stack must be removed. We continue popping until the stack is empty or the node at the top is greater than or equal to `current`. Then, we push `current` onto the stack. This ensures the stack always holds a sequence of nodes with decreasing values. After one pass, the nodes remaining in the stack are precisely the ones that should be in the final list, but in reverse order. A second pass over the stack elements allows us to rebuild the linked list in the correct order.

```java
import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 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; }
 * }
 */
class Solution {
    public ListNode removeNodes(ListNode head) {
        Deque<ListNode> stack = new ArrayDeque<>();
        ListNode current = head;

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

        ListNode newHead = null;
        while (!stack.isEmpty()) {
            ListNode node = stack.pop();
            node.next = newHead;
            newHead = node;
        }

        return newHead;
    }
}
```
### Algorithm
*   Initialize an empty stack, which will store `ListNode` objects.
*   Iterate through the linked list from `head` to `tail` with a `current` pointer.
*   For each `current` node:
    *   While the stack is not empty and the value of the node at the top of the stack (`stack.peek().val`) is less than `current.val`, pop from the stack. This step removes all nodes that are followed by a greater node (`current`).
    *   After the loop, push the `current` node onto the stack.
*   After iterating through the entire list, the stack contains the nodes of the final list, but in reverse order.
*   To construct the final list, create a new `head` (initially `null`). Repeatedly pop from the stack, and for each popped node, set its `next` pointer to the current `head` and then update `head` to be the popped node. This reverses the order and links the nodes correctly.
*   Return the new `head`.

## Two-Pass with List Reversal
This is the most optimal approach in terms of both time and space complexity. The key idea is to transform the problem by reversing the linked list. After reversing, the condition 'a node with a greater value to the right' becomes 'a node with a greater value to the left'. This new problem is much easier to solve in a single pass. After filtering the nodes in the reversed list, we reverse it back to get the final answer.
**Time:** O(N) - The algorithm consists of three passes over the list (reverse, filter, reverse back), each taking O(N) time. The total time complexity is O(N) + O(N) + O(N) = O(N). · **Space:** O(1) - The list reversal and filtering are done in-place, using only a few extra pointers.
**Pros:** Optimal solution with O(N) time complexity.; Most space-efficient solution with O(1) extra space.
**Cons:** The logic involves multiple steps (two reversals and a traversal), which can be slightly more complex to implement correctly compared to a single-pass recursive solution.
### Explanation
First, we reverse the entire linked list. For an input of `[5,2,13,3,8]`, this gives us `[8,3,13,2,5]`. Now, we can iterate through this reversed list and keep only the nodes that form a non-increasing sequence when read from left to right. We can do this by keeping track of the maximum value seen so far. We start with `max_so_far = 8`. Then we see `3`, which is less than `8`, so we remove it. Then we see `13`, which is greater than `8`, so we keep it and update `max_so_far = 13`. Then we see `2` and `5`, both less than `13`, so they are removed. The resulting list is `[8, 13]`. Finally, we reverse this list again to get `[13, 8]`, which is the correct output. This entire process takes two full passes over the list data (two reversals and one filtering pass), resulting in linear time complexity, but crucially, it uses only a constant amount of extra space.

```java
/**
 * 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; }
 * }
 */
class Solution {
    public ListNode removeNodes(ListNode head) {
        // Step 1: Reverse the linked list
        ListNode reversedHead = reverseList(head);

        ListNode current = reversedHead;
        int maxVal = Integer.MIN_VALUE;
        ListNode prev = null;

        // Step 2: Traverse the reversed list and remove nodes
        while (current != null) {
            if (current.val >= maxVal) {
                // Keep this node
                maxVal = current.val;
                prev = current;
            } else {
                // Remove this node by skipping it
                prev.next = current.next;
            }
            current = current.next;
        }

        // Step 3: Reverse the list again to get the final result
        return reverseList(reversedHead);
    }

    private ListNode reverseList(ListNode node) {
        ListNode prev = null;
        ListNode current = node;
        while (current != null) {
            ListNode nextTemp = current.next;
            current.next = prev;
            prev = current;
            current = nextTemp;
        }
        return prev;
    }
}
```
### Algorithm
*   **Step 1: Reverse the list.** Implement a helper function to reverse the linked list. Call it on the original `head`. The original tail is now the new head.
*   **Step 2: Filter the nodes.** Traverse the reversed list. Keep track of the maximum value seen so far (`max_so_far`), initialized to the value of the new head.
    *   Use a `prev` pointer to track the last node that was kept and a `current` pointer to iterate.
    *   If `current.val` is less than `max_so_far`, it means this node has a greater value to its left (which was its right in the original list). Remove it by setting `prev.next = current.next`.
    *   If `current.val` is greater than or equal to `max_so_far`, keep this node. Update `max_so_far = current.val` and advance `prev` to `current`.
*   **Step 3: Reverse the list again.** The filtered list is now correct but in reverse order. Call the reverse function again on the head of this modified list to restore the original relative order of the kept nodes.

# Solutions
### Java

```java
/** * 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; } * } */ class Solution { public ListNode removeNodes ( ListNode head ) { List < Integer > nums = new ArrayList <>(); while ( head != null ) { nums . add ( head . val ); head = head . next ; } Deque < Integer > stk = new ArrayDeque <>(); for ( int v : nums ) { while (! stk . isEmpty () && stk . peekLast () < v ) { stk . pollLast (); } stk . offerLast ( v ); } ListNode dummy = new ListNode (); head = dummy ; while (! stk . isEmpty ()) { head . next = new ListNode ( stk . pollFirst ()); head = head . next ; } return dummy . next ; } }
```

### CPP

```cpp
/** * 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 > nums ; while ( head ) { nums . emplace_back ( head -> val ); head = head -> next ; } vector < int > stk ; for ( int v : nums ) { while ( ! stk . empty () && stk . back () < v ) { stk . pop_back (); } stk . push_back ( v ); } ListNode * dummy = new ListNode (); head = dummy ; for ( int v : stk ) { head -> next = new ListNode ( v ); head = head -> next ; } return dummy -> next ; } };
```

### Python

```python
# 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 ]: nums = [] while head : nums . append ( head . val ) head = head . next stk = [] for v in nums : while stk and stk [ - 1 ] < v : stk . pop () stk . append ( v ) dummy = ListNode () head = dummy for v in stk : head . next = ListNode ( v ) head = head . next return dummy . next
```