Problem Description

You are given the head of a linked list. Your task is to remove every node that has at least one node with a greater value somewhere to its right in the linked list.

In other words, for each node in the linked list, if there exists any node to its right (later in the list) that has a greater value, that node should be removed from the list.

After removing all such nodes, return the head of the modified linked list.

For example, if you have a linked list 5 -> 2 -> 13 -> 3 -> 8:

• Node with value 5 should be removed because 13 (which is to its right) is greater than 5
• Node with value 2 should be removed because 13 (which is to its right) is greater than 2
• Node with value 13 stays because no node to its right is greater than 13
• Node with value 3 should be removed because 8 (which is to its right) is greater than 3
• Node with value 8 stays because there are no nodes to its right

The resulting linked list would be 13 -> 8.

The key insight is that a node survives only if there is no greater value to its right in the original linked list.

Intuition

When we need to keep only nodes that don't have any greater value to their right, we can think about this problem from a different angle: which nodes should we keep?

A node should be kept if and only if all nodes to its right have values less than or equal to it. This means we're essentially looking for nodes that form a non-increasing sequence when read from right to left.

If we traverse the linked list from left to right and look at the values, we want to maintain only those values that won't be "overshadowed" by any future larger values. This naturally leads us to think about a monotonic stack.

Consider what happens when we encounter each value:

• If a new value is larger than some previous values, those previous values should be removed because they have a greater value to their right (the current value).
• If a new value is smaller than or equal to all previous kept values, it might survive (unless an even larger value appears later).

This pattern matches exactly with a monotonic decreasing stack: when we see a new value, we pop all smaller values from the stack (they can't be in the final answer), then push the current value. The stack maintains values in decreasing order, and these are exactly the values that survive in the final linked list.

For example, with [5, 2, 13, 3, 8]:

• Start with 5: stack = [5]
• See 2: it's smaller, stack = [5, 2]
• See 13: it's larger than both, pop them all, stack = [13]
• See 3: it's smaller, stack = [13, 3]
• See 8: it's larger than 3 but not 13, pop 3, stack = [13, 8]

The final stack [13, 8] gives us our answer.

Learn more about Stack, Recursion, Linked List and Monotonic Stack patterns.

Solution Approach

The solution implements the monotonic stack approach in two phases:

Phase 1: Convert Linked List to Array

First, we traverse the linked list and store all node values in an array nums. This allows us to process the values more easily:

nums = []
while head:
    nums.append(head.val)
    head = head.next

Phase 2: Build Monotonic Decreasing Stack

We iterate through the array nums and maintain a stack stk that keeps values in non-increasing order from bottom to top:

stk = []
for v in nums:
    while stk and stk[-1] < v:
        stk.pop()
    stk.append(v)

For each value v:

• While the stack is not empty and the top element is smaller than v, we pop the stack. These popped elements cannot be in the final answer because they have a greater value (v) to their right.
• After removing all smaller elements, we push v onto the stack.

This ensures the stack maintains a monotonic decreasing property - each element is greater than or equal to the elements above it.

Phase 3: Reconstruct the Linked List

Finally, we build a new linked list from the values in the stack:

dummy = ListNode()
head = dummy
for v in stk:
    head.next = ListNode(v)
    head = head.next
return dummy.next

We use a dummy node to simplify the list construction. We iterate through the stack (which now contains only the surviving values in the correct order) and create new nodes for each value.

Time and Space Complexity:

• Time Complexity: O(n) where n is the number of nodes. Each node is visited once during the initial traversal, and each value is pushed and popped from the stack at most once.
• Space Complexity: O(n) for storing the array nums and the stack stk.

The algorithm elegantly solves the problem by recognizing that the nodes we want to keep form a monotonic decreasing sequence, which can be efficiently maintained using a stack data structure.

Example Walkthrough

Let's walk through the solution with the linked list: 4 -> 6 -> 3 -> 7 -> 2

Step 1: Convert to Array First, we traverse the linked list and store values in an array:

• nums = [4, 6, 3, 7, 2]

Step 2: Build Monotonic Decreasing Stack Now we process each value and maintain a stack with non-increasing values:

1. Process 4:

   • Stack is empty, push 4
   • Stack: [4]

2. Process 6:

   • Top of stack is 4, which is less than 6
   • Pop 4 (it has a greater value 6 to its right)
   • Stack is now empty, push 6
   • Stack: [6]

3. Process 3:

   • Top of stack is 6, which is greater than 3
   • No popping needed, push 3
   • Stack: [6, 3]

4. Process 7:

   • Top of stack is 3, which is less than 7
   • Pop 3 (it has a greater value 7 to its right)
   • Top of stack is now 6, which is less than 7
   • Pop 6 (it has a greater value 7 to its right)
   • Stack is now empty, push 7
   • Stack: [7]

5. Process 2:

   • Top of stack is 7, which is greater than 2
   • No popping needed, push 2
   • Stack: [7, 2]

Step 3: Reconstruct Linked List Create a new linked list from stack values [7, 2]:

• Final result: 7 -> 2

Verification:

• Node 4 was removed (has 6, 7 to its right which are greater)
• Node 6 was removed (has 7 to its right which is greater)
• Node 3 was removed (has 7 to its right which is greater)
• Node 7 remains (no greater values to its right)
• Node 2 remains (no values to its right)

The algorithm correctly identifies that only nodes with values 7 and 2 should remain in the final linked list.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of three main operations:

• First traversal of the linked list to extract values into the nums array: O(n)
• Processing each element in nums with the monotonic stack: Each element is pushed once and popped at most once, resulting in O(n) operations
• Reconstructing the linked list from the stack: O(k) where k ≤ n is the size of the final stack

Total time complexity: O(n) + O(n) + O(k) = O(n)

Space Complexity: O(n)

The algorithm uses additional space for:

• The nums array storing all node values: O(n)
• The stk monotonic stack which can contain at most n elements: O(n)
• The new linked list nodes created from the stack elements: O(k) where k ≤ n

Total space complexity: O(n) + O(n) + O(k) = O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Attempting In-Place Modification Without Proper Pointer Management

A common mistake is trying to modify the linked list in-place while traversing it forward. This approach fails because:

1. When you determine a node should be removed, you need access to its previous node to update the links
2. Traversing forward makes it difficult to know if a current node should be kept until you've seen all nodes to its right
3. Managing multiple pointers while modifying the list structure can lead to lost references or broken links

Incorrect Approach Example:

def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
    current = head
    prev = None
  
    while current:
        # Check if any node to the right is greater
        temp = current.next
        should_remove = False
        while temp:
            if temp.val > current.val:
                should_remove = True
                break
            temp = temp.next
      
        if should_remove:
            if prev:
                prev.next = current.next
            else:
                head = current.next
        else:
            prev = current
      
        current = current.next
  
    return head

This approach has O(n²) time complexity and is error-prone with pointer management.

Pitfall 2: Forgetting Edge Cases

Common edge cases that are often overlooked:

1. Empty list or single node: The algorithm should handle None or a single-node list gracefully
2. All nodes removed: If the list is strictly increasing (e.g., 1->2->3->4), only the last node remains
3. No nodes removed: If the list is non-increasing (e.g., 4->3->2->1), all nodes remain

Solution to Avoid These Pitfalls

The provided solution elegantly avoids these issues by:

1. Converting to array first: This eliminates pointer management complexity and allows easy access to all values
2. Using monotonic stack pattern: This well-established pattern ensures correctness and optimal O(n) complexity
3. Reconstructing from scratch: Building a new linked list is cleaner than in-place modification and avoids pointer confusion

Alternative Correct Approach - Reverse Processing: If you want to work directly with the linked list without converting to an array, consider processing from right to left:

def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
    # Reverse the linked list first
    def reverse(node):
        prev = None
        while node:
            next_node = node.next
            node.next = prev
            prev = node
            node = next_node
        return prev
  
    # Reverse the list
    head = reverse(head)
  
    # Keep track of maximum seen so far
    max_val = float('-inf')
    dummy = ListNode()
    current = dummy
  
    # Process from right to left (now left to right in reversed list)
    while head:
        if head.val >= max_val:
            max_val = head.val
            # Keep this node
            temp = head.next
            head.next = current.next
            current.next = head
            head = temp
        else:
            # Skip this node
            head = head.next
  
    return dummy.next

This approach maintains O(n) time complexity while working directly with the linked list structure.