Remove Nodes That Have a Greater Value on Their Right in a Linked List

Problem Statement

Given a singly linked list, delete all nodes such that:

If a node has any greater value node on its right side, it must be removed.

Return the modified linked list.

Understanding the Problem

For every node, we need to determine:

Is there any node on its right with a greater value?
If yes, remove the current node.
If no, keep the current node.

Example

Input

12 -> 15 -> 10 -> 11 -> 5 -> 6 -> 2 -> 3

Output

15 -> 11 -> 6 -> 3

Explanation

12 is removed because 15 exists on its right.
10 is removed because 11 exists on its right.
5 is removed because 6 exists on its right.
2 is removed because 3 exists on its right.

The remaining nodes are:

15 -> 11 -> 6 -> 3

Key Idea

For each node, we need to check whether there is a larger value somewhere on its right side.

A direct approach would repeatedly scan the right side of every node, but that is inefficient.

Instead, we use a clever observation:

If we reverse the linked list, the right side becomes the left side.

This allows us to process the list in a single pass while maintaining the maximum value seen so far.

Naive Approach

For every node:

Traverse all nodes on its right.
Check whether a greater value exists.
Remove the node if necessary.

Pseudocode

for each node:
    scan all nodes on the right

    if greater value exists:
        delete current node

Time Complexity

O(n²)

This is too slow for large linked lists.

Optimal Approach

Important Insight

Instead of repeatedly checking the right side, reverse the linked list.

After reversing:

Right-side nodes become left-side nodes.
We can track the maximum value encountered so far.
Any node smaller than the maximum can be removed immediately.

Step 1: Reverse the Linked List

Original list:

12 -> 15 -> 10 -> 11 -> 5 -> 6 -> 2 -> 3

After reversing:

3 -> 2 -> 6 -> 5 -> 11 -> 10 -> 15 -> 12

Now we are effectively processing the original list from right to left.

Step 2: Traverse the Reversed List

Maintain:

maxNode

which stores the maximum value seen so far.

Processing Rules

Case 1: Current Node Is Smaller Than maxNode

node.data < maxNode.data

Remove the node because a greater value existed on its right in the original list.

Case 2: Current Node Is Greater Than or Equal to maxNode

Keep the node and update:

maxNode = current node

Example Walkthrough

Reversed List

3 -> 2 -> 6 -> 5 -> 11 -> 10 -> 15 -> 12

Processing

Keep:

Remove:

because 3 is the maximum seen so far.

Keep:

Remove:

because 6 is larger.

Keep:

Remove:

because 11 is larger.

Keep:

Remove:

because 15 is larger.

Remaining reversed list:

3 -> 6 -> 11 -> 15

Step 3: Reverse Again

Reverse the filtered list:

15 -> 11 -> 6 -> 3

This restores the original order.

Why This Approach Works

After reversing:

Every node only needs to be compared with the maximum value seen so far.
If a larger value has already appeared, that means a greater value existed on the right in the original list.
Such nodes can be removed immediately.

This eliminates the need for repeated scanning.

Java Solution

class Solution {

    Node reverse(Node head) {
        Node prev = null;
        Node curr = head;

        while (curr != null) {
            Node next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    Node compute(Node head) {
        if (head == null || head.next == null) return head;

        // Step 1: Reverse list
        head = reverse(head);

        // Step 2: Remove nodes smaller than max seen
        Node curr = head;
        Node maxNode = head;

        while (curr != null && curr.next != null) {
            if (curr.next.data < maxNode.data) {
                curr.next = curr.next.next;
            } else {
                curr = curr.next;
                maxNode = curr;
            }
        }

        // Step 3: Reverse again
        return reverse(head);
    }
}

Complexity Analysis

Time Complexity

The list is traversed a constant number of times:

First reverse: O(n)
Filtering pass: O(n)
Second reverse: O(n)

Overall:

O(n)

Space Complexity

No additional data structures are used.

O(1)

Pattern Recognition

Whenever a linked list problem requires:

Comparing nodes with elements on the right.
Finding greater values on the right.
Maintaining suffix maximums.
Removing nodes based on future values.

Consider this technique:

Reverse the linked list and process from the opposite direction.

This pattern frequently transforms difficult right-side comparisons into simple left-side traversals.

Key Takeaway

The crucial observation is that checking every node against all nodes on its right is inefficient. By reversing the linked list, the problem becomes one of maintaining the maximum value seen so far. Nodes smaller than this maximum can be removed immediately, reducing the complexity from O(n²) to O(n).

Summary

To remove nodes that have a greater value on their right, reverse the linked list and process it from the original right-to-left direction. Maintain the maximum value seen so far and remove any node smaller than this maximum. Finally, reverse the list again to restore the original order. This elegant technique solves the problem in O(n) time and O(1) extra space.