LeetCode 2487 - Remove Nodes From Linked List

LeetCode Problem 2487

Difficulty: 🟡 Medium
Topics: Linked List, Stack, Recursion, Monotonic Stack

Solution

Problem Understanding

The problem gives us the head of a singly linked list and asks us to remove every node that has a strictly greater value somewhere to its right.

In other words, for each node, we must determine whether there exists another node later in the list whose value is larger. If such a node exists, the current node should be deleted. Otherwise, the node should remain in the final linked list.

For example, consider the list:

5 -> 2 -> 13 -> 3 -> 8

The node 5 should be removed because 13 appears later and is greater than 5.

The node 2 should also be removed because 13 is greater.

The node 13 stays because no larger value exists to its right.

The node 3 is removed because 8 is greater and appears later.

The node 8 stays because it is the final node.

The resulting list becomes:

13 -> 8

The constraints are important:

• The list can contain up to 10^5 nodes.
• Node values can also be as large as 10^5.

These constraints immediately tell us that an O(n^2) solution may be too slow in the worst case. A quadratic algorithm on 100000 elements would require around 10^10 operations, which is far beyond acceptable limits for LeetCode.

The input is guaranteed to contain at least one node, so we do not need to handle a completely empty list from the problem constraints, although robust implementations can still safely support None or nil.

Several edge cases are important:

• A strictly increasing list such as [1,2,3,4], where every node except the last must be removed.
• A strictly decreasing list such as [9,7,5,3], where no nodes are removed.
• Duplicate values such as [5,5,5], where no node is removed because the condition requires a strictly greater value.
• A single-node list, where the node always remains.

Approaches

Brute Force Approach

The most direct solution is to examine every node and search all nodes to its right to determine whether a greater value exists.

For each node:

1. Traverse the remaining portion of the list.
2. If a larger value is found, remove the current node.
3. Otherwise, keep it.

This approach is straightforward and clearly correct because it explicitly checks the problem condition for every node.

However, its performance is poor. For each node, we may scan nearly the entire remainder of the list. If the list contains n nodes, the total work becomes:

(n - 1) + (n - 2) + ... + 1

which is O(n^2).

With up to 100000 nodes, this solution is too slow.

Optimal Approach

The key observation is that a node should remain only if it is greater than or equal to every value to its right.

This means that if we traverse the list from right to left, we can keep track of the maximum value seen so far.

• If the current node's value is smaller than the maximum seen to the right, we remove it.
• Otherwise, we keep it and update the maximum.

The challenge is that singly linked lists do not support reverse traversal.

There are several ways to solve this:

• Reverse the linked list first
• Use recursion
• Use a monotonic stack

A very clean and efficient approach is:

1. Reverse the linked list.
2. Traverse from left to right while maintaining the maximum value seen so far.
3. Remove nodes smaller than that maximum.
4. Reverse the list again to restore original order.

This gives an O(n) solution because every node is processed a constant number of times.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	For every node, scan all nodes to the right
Optimal	O(n)	O(1)	Reverse list, track maximum from the right

Algorithm Walkthrough

Optimal Reverse-and-Filter Algorithm

1. Reverse the linked list.

Since we need information about nodes to the right, reversing the list transforms the problem into processing nodes from the original right side toward the left side.

Example:

Original:  5 -> 2 -> 13 -> 3 -> 8
Reversed:  8 -> 3 -> 13 -> 2 -> 5

2. Initialize the maximum value seen so far.

The first node in the reversed list always remains because nothing existed to its right in the original list.

We store:

max_value = reversed_head.val

3. Traverse the reversed list.

For each node:

• If the next node's value is smaller than max_value, remove it.
• Otherwise, keep it and update max_value.

This works because max_value represents the greatest value originally to the right of the current node. 4. Remove nodes by skipping pointers.

Since this is a singly linked list, deletion is performed by changing:

current.next = current.next.next

5. Reverse the filtered list again.

The remaining nodes are currently in reversed order. Reversing once more restores the original left-to-right order. 6. Return the final head.

Why it works

The algorithm maintains an invariant while traversing the reversed list:

max_value always stores the largest value among all previously visited nodes in the reversed traversal.

Because reversing swaps left and right relationships, previously visited nodes in the reversed list correspond exactly to nodes originally to the right.

Therefore:

• If a node's value is smaller than max_value, a greater node existed to its right originally, so it must be removed.
• Otherwise, it should remain.

This guarantees correctness for every node.

Python Solution

# 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]:
        
        def reverse(node: Optional[ListNode]) -> Optional[ListNode]:
            prev = None
            current = node
            
            while current:
                next_node = current.next
                current.next = prev
                prev = current
                current = next_node
            
            return prev
        
        # Reverse the list
        head = reverse(head)
        
        # Remove nodes smaller than max seen so far
        max_value = head.val
        current = head
        
        while current and current.next:
            if current.next.val < max_value:
                current.next = current.next.next
            else:
                current = current.next
                max_value = current.val
        
        # Reverse again to restore order
        return reverse(head)

The implementation starts with a helper function called reverse, which reverses a singly linked list iteratively using three pointers:

• prev
• current
• next_node

This helper is used twice, once before filtering and once after filtering.

After reversing the list, the first node automatically survives because it originally had no nodes to its right. Its value initializes max_value.

The main traversal checks current.next rather than current. This makes node deletion simpler because we can remove the next node directly by updating pointers.

If current.next.val is less than max_value, the node is skipped. Otherwise, the node becomes part of the final list, so we advance current and update max_value.

Finally, the filtered reversed list is reversed again to restore the original ordering.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNodes(head *ListNode) *ListNode {
    
    reverse := func(node *ListNode) *ListNode {
        var prev *ListNode
        current := node
        
        for current != nil {
            nextNode := current.Next
            current.Next = prev
            prev = current
            current = nextNode
        }
        
        return prev
    }
    
    // Reverse the list
    head = reverse(head)
    
    // Remove nodes smaller than max seen so far
    maxValue := head.Val
    current := head
    
    for current != nil && current.Next != nil {
        if current.Next.Val < maxValue {
            current.Next = current.Next.Next
        } else {
            current = current.Next
            maxValue = current.Val
        }
    }
    
    // Reverse again to restore order
    return reverse(head)
}

The Go implementation follows exactly the same algorithmic structure as the Python version.

One notable difference is Go's explicit pointer handling. Instead of None, Go uses nil. Pointer updates are otherwise identical.

The reversal helper uses local pointer variables and iterative traversal, which avoids recursion depth concerns.

Since node values are at most 10^5, integer overflow is not a concern in Go's standard int type.

Worked Examples

Example 1

Input:

5 -> 2 -> 13 -> 3 -> 8

Step 1: Reverse the list

8 -> 3 -> 13 -> 2 -> 5

Initialize:

max_value = 8
current = 8

Step 2: Traverse and remove

Current Node	Next Node	max_value	Action	Resulting List
8	3	8	Remove 3	8 -> 13 -> 2 -> 5
8	13	8	Keep 13, update max	8 -> 13 -> 2 -> 5
13	2	13	Remove 2	8 -> 13 -> 5
13	5	13	Remove 5	8 -> 13

Step 3: Reverse again

13 -> 8

Final output:

[13,8]

Example 2

Input:

1 -> 1 -> 1 -> 1

Step 1: Reverse

1 -> 1 -> 1 -> 1

Initialize:

max_value = 1

Step 2: Traverse

Current Node	Next Node	max_value	Action
1	1	1	Keep
1	1	1	Keep
1	1	1	Keep

No nodes are removed.

Step 3: Reverse again

The list remains:

1 -> 1 -> 1 -> 1

Final output:

[1,1,1,1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited a constant number of times
Space	O(1)	Only a few pointer variables are used

The list is reversed twice and traversed once during filtering. Even though there are multiple passes, each pass is linear, so the total runtime remains O(n).

The algorithm modifies the linked list in place and uses only constant extra memory, making the auxiliary space complexity O(1).

Test Cases

# Helper utilities for testing

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    dummy = ListNode()
    current = dummy
    
    for value in values:
        current.next = ListNode(value)
        current = current.next
    
    return dummy.next

def to_list(head):
    result = []
    
    while head:
        result.append(head.val)
        head = head.next
    
    return result

class Solution:
    def removeNodes(self, head):
        
        def reverse(node):
            prev = None
            current = node
            
            while current:
                next_node = current.next
                current.next = prev
                prev = current
                current = next_node
            
            return prev
        
        head = reverse(head)
        
        max_value = head.val
        current = head
        
        while current and current.next:
            if current.next.val < max_value:
                current.next = current.next.next
            else:
                current = current.next
                max_value = current.val
        
        return reverse(head)

solution = Solution()

# Example 1
head = build_list([5, 2, 13, 3, 8])
assert to_list(solution.removeNodes(head)) == [13, 8]  # standard mixed case

# Example 2
head = build_list([1, 1, 1, 1])
assert to_list(solution.removeNodes(head)) == [1, 1, 1, 1]  # all equal values

# Strictly increasing
head = build_list([1, 2, 3, 4])
assert to_list(solution.removeNodes(head)) == [4]  # only largest survives

# Strictly decreasing
head = build_list([9, 7, 5, 3])
assert to_list(solution.removeNodes(head)) == [9, 7, 5, 3]  # no removals

# Single node
head = build_list([42])
assert to_list(solution.removeNodes(head)) == [42]  # minimal input

# Duplicate maximums
head = build_list([5, 2, 5, 2, 5])
assert to_list(solution.removeNodes(head)) == [5, 5, 5]  # equal maximums stay

# Remove middle nodes
head = build_list([10, 4, 6, 3, 2])
assert to_list(solution.removeNodes(head)) == [10, 6, 3, 2]  # partial removals

# Large tail maximum
head = build_list([1, 1, 1, 100])
assert to_list(solution.removeNodes(head)) == [100]  # tail dominates all

Test	Why
[5,2,13,3,8]	Standard mixed example
[1,1,1,1]	Verifies equal values are not removed
[1,2,3,4]	Checks strictly increasing input
[9,7,5,3]	Checks strictly decreasing input
[42]	Validates single-node behavior
[5,2,5,2,5]	Ensures duplicate maximums remain
[10,4,6,3,2]	Tests partial removals in the middle
[1,1,1,100]	Verifies a large tail value removes everything before it

Edge Cases

Single-Node List

A list containing only one node is an important boundary condition. Since no nodes exist to the right, the node must always remain.

A buggy implementation might accidentally remove it during reversal or filtering. This implementation handles the case naturally because the traversal loop never removes the only node.

Strictly Increasing List

Consider:

1 -> 2 -> 3 -> 4

Every node except the final one has a greater value to its right.

This case is useful because it forces the algorithm to remove many consecutive nodes. Incorrect pointer updates can easily break the list structure here.

The implementation safely removes nodes by updating current.next without advancing current after deletion.

Duplicate Values

Consider:

5 -> 5 -> 5

The condition requires a strictly greater value, not a greater-or-equal value.

A common mistake is using <= instead of <, which would incorrectly remove equal values.

This implementation removes a node only when:

current.next.val < max_value

Equal values remain in the list correctly.

Strictly Decreasing List

Consider:

9 -> 7 -> 5 -> 3

No node has a greater value to its right, so the entire list should remain unchanged.

This edge case verifies that the algorithm does not remove nodes unnecessarily and correctly updates max_value as traversal proceeds.