---
###### tags: `Leetcode`
---
# Leetcode 2487. Remove Nodes From Linked List

[link](https://leetcode.com/problems/remove-nodes-from-linked-list/)

---

You are given the head of a linked list.

Remove every node which has a node with a strictly 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

---

The method iterates through the nodes in the input linked list using a while loop, and for each node, it compares its value to the value of the top element in the stack. If the node's value is greater than the stack's top value, the stack's top element is popped until the node's value is no longer greater than the stack's top value. The current node is then added to the stack, and its reference is added to the next attribute of the last element in the stack.

Finally, the method returns the reference to the next node of the dummy node, which points to the beginning of the modified linked list with some nodes removed.

#### Solution 1

# 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]:
        dummy = ListNode(inf)
        stack = [dummy]

        while head:
            while stack and head.val > stack[-1].val:
                stack.pop()
            stack[-1].next = head
            stack.append(head)
            head = head.next

        return dummy.next
        

O(T): O(N^2)
O(S): O(N)