# 2487. Remove Nodes From Linked List

## Description

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:

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

## Solutions

Solution 1: Monotonic Stack Simulation

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.

• /**
* 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 {
List<Integer> nums = new ArrayList<>();
}
Deque<Integer> stk = new ArrayDeque<>();
for (int v : nums) {
while (!stk.isEmpty() && stk.peekLast() < v) {
stk.pollLast();
}
stk.offerLast(v);
}
ListNode dummy = new ListNode();
while (!stk.isEmpty()) {
}
return dummy.next;
}
}

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

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


• /**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
nums := []int{}
}
stk := []int{}
for _, v := range nums {
for len(stk) > 0 && stk[len(stk)-1] < v {
stk = stk[:len(stk)-1]
}
stk = append(stk, v)
}
dummy := &ListNode{}
for _, v := range stk {
}
return dummy.Next
}

• /**
* class ListNode {
*     val: number
*     next: ListNode | null
*     constructor(val?: number, next?: ListNode | null) {
*         this.val = (val===undefined ? 0 : val)
*         this.next = (next===undefined ? null : next)
*     }
* }
*/

function removeNodes(head: ListNode | null): ListNode | null {
const nums = [];
}
const stk: number[] = [];
for (const v of nums) {
while (stk.length && stk.at(-1)! < v) {
stk.pop();
}
stk.push(v);
}
const dummy = new ListNode();