Watch 10 video solutions for Remove Nodes From Linked List, a medium level problem involving Linked List, Stack, Recursion. This walkthrough by NeetCodeIO has 15,106 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |