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:
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:
[1, 105].1 <= Node.val <= 105Problem Overview: You are given the head of a singly linked list. Remove every node that has a node with a strictly greater value somewhere to its right. The remaining list must preserve the original order. The core challenge is efficiently determining whether a future node contains a larger value while traversing a linked list.
Approach 1: Reverse Traversal Using a Stack (O(n) time, O(n) space)
This approach simulates looking at the list from right to left using a stack. Traverse the list from left to right while maintaining a monotonic decreasing structure. When you encounter a node, repeatedly pop elements from the stack while the stack's top value is smaller than the current node's value. Those nodes must be removed because a larger value exists to their right. After processing, push the current node onto the stack. Once traversal finishes, rebuild the linked list from the stack so that only nodes that never encountered a larger value to their right remain.
The key insight is the monotonic property: the stack always keeps nodes in decreasing order of values. Any smaller node before a larger one becomes invalid and is removed immediately. Each node is pushed and popped at most once, giving O(n) time complexity and O(n) auxiliary space. This approach is straightforward and maps naturally to a monotonic stack pattern used in many array and list problems.
Approach 2: Recursion and Backtracking (O(n) time, O(n) space)
Recursion provides a clean way to process the list from right to left without explicitly reversing it. Recursively process the rest of the list first, which returns the filtered suffix of the list. When the recursion unwinds, compare the current node's value with the head of the processed suffix. If the suffix head contains a larger value, the current node should be removed because a greater value exists to its right. Otherwise, attach the filtered suffix after the current node and keep it.
This works because recursion naturally evaluates the list in reverse order. By the time you process a node, the entire right side has already been cleaned and the maximum candidate is visible at the returned head. Each node is visited exactly once, resulting in O(n) time complexity. The recursion stack uses O(n) space in the worst case. This approach is elegant but relies on the call stack, which may not be ideal in environments with strict recursion limits.
Recommended for interviews: The monotonic stack approach is typically the expected solution. It demonstrates recognition of the "next greater element" pattern and works in linear time with predictable memory usage. Showing the recursive solution afterward highlights a deeper understanding of how to process recursion problems that require reverse traversal of a linked list.
This approach involves reversing the linked list and using a stack to maintain the maximum values encountered so far. This allows us to easily determine which nodes have a greater value to their right.
The code defines a function removeNodes that takes a singly linked list and removes nodes that have a node with a greater value to their right. It uses a stack to keep track of potential candidates for the resulting list, reconstructing the list after determining the correct elements.
Time Complexity: O(n), where n is the number of nodes in the linked list since each node is processed twice.
Space Complexity: O(n), due to the use of an additional stack to store nodes.
This approach uses recursion to traverse the list and solve the problem recursively by backtracking from the end of the list to the start.
The recursive solution traverses to the end of the list, then checks if the current node should be part of the result or skipped based on the value comparison of its next node, ensuring that nodes with greater values are prioritized.
C++
JavaScript
Time Complexity: O(n) - as each node is visited exactly once.
Space Complexity: O(n) - due to recursive stack space used during function calls.
We can first store the node values of the linked list into an array nums. Then, we traverse the array nums, maintaining a stack stk that is monotonically decreasing from the bottom to the top. If the current element is larger than the top element of the stack, we pop the top element of the stack until the current element is less than or equal to the top element, and then we push the current element into the stack.
Finally, we construct the resulting linked list from the bottom to the top of the stack, which is the answer.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the linked list.
We can also directly traverse the linked list without using the array nums, maintaining a stack stk that is monotonically decreasing from the bottom to the top. If the current element is larger than the top element of the stack, we pop the top element of the stack until the current element is less than or equal to the top element. Then, if the stack is not empty, we set the next pointer of the top element of the stack to the current element. Otherwise, we set the next pointer of the dummy head node of the answer linked list to the current element. Finally, we push the current element into the stack and continue to traverse the linked list.
After the traversal, we return the next pointer of the dummy head node as the answer.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the linked list.
Python
Java
C++
Go
TypeScript
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Reverse Traversal Using a Stack | Time Complexity: O(n), where n is the number of nodes in the linked list since each node is processed twice. |
| Approach 2: Recursion and Backtracking | Time Complexity: O(n) - as each node is visited exactly once. |
| Monotonic Stack Simulation | — |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Reverse Traversal Using Stack | O(n) | O(n) | Best general solution. Efficient for large lists and clearly demonstrates the monotonic stack pattern. |
| Recursion and Backtracking | O(n) | O(n) | Good when you want a clean right-to-left evaluation without explicitly reversing or using a stack. |
Remove Nodes From Linked List - Leetcode 2487 - Python • NeetCodeIO • 15,106 views views
Watch 9 more video solutions →Practice Remove Nodes From Linked List with our built-in code editor and test cases.
Practice on FleetCode