Problem Statement in English

You’re given a linked list.

Your task is to remove all nodes that have a value greater than them to their right.

You must return the modified linked list.

Approach

This is another classic monotonic stack problem.

Think about it. What they really want is for you to make an increasing stack.

So,

  • We keep popping from the stack until we find a node that is greater than the current node.

  • We push the current node onto the stack.

  • We set the next of the last node in the stack to the current node.

And we’re done.

Solution in Python


class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        stack = []
        temp = head

        while temp:
            while stack and stack[-1].val < temp.val:
                stack.pop()

            if stack:
                stack[-1].next = temp
            stack.append(temp)

            temp = temp.next

        return stack[0]

Complexity

  • Time: O(n)O(n)
    Since we iterate through the linked list once.

  • Space: O(n)O(n)
    Since we use a stack to store the nodes.

And we are done.