Delete Nodes Which Have a Greater Value on Right Side

Problem Statement

Given a singly linked list, remove all nodes which have a greater value on the right side. The resulting list should be sorted in decreasing order from left to right.

Example

Input: 12 -> 15 -> 10 -> 11 -> 5 -> 6 -> 2 -> 3
Output: 15 -> 11 -> 6 -> 3

Explanation:
- 12 is removed because 15 on right is greater
- 15 stays (nothing greater on right)
- 10 is removed because 11 on right is greater
- 11 stays (max element till end starting from 11)
- 5 is removed because 6 on right is greater
- 6 stays
- 2 is removed because 3 on right is greater
- 3 stays (it's the last element)

Brute Force Approach

Intuition

For each node, traverse all nodes to its right to check if any node has a greater value. If found, mark the node for deletion.

Algorithm

For each node, scan all nodes to its right
If any right node has greater value, delete current node
Continue until all nodes are processed

Code

java

class Node {
    int data;
    Node next;
    
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class DeleteGreaterRightBrute {
    public static boolean hasGreaterOnRight(Node node) {
        Node curr = node.next;
        while (curr != null) {
            if (curr.data > node.data) {
                return true;
            }
            curr = curr.next;
        }
        return false;
    }
    
    public static Node deleteNodesBruteForce(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        // Create dummy node
        Node dummy = new Node(Integer.MAX_VALUE);
        dummy.next = head;
        
        Node prev = dummy;
        Node curr = head;
        
        while (curr != null) {
            if (hasGreaterOnRight(curr)) {
                // Delete curr
                prev.next = curr.next;
                curr = curr.next;
            } else {
                prev = curr;
                curr = curr.next;
            }
        }
        
        return dummy.next;
    }
    
    public static void printList(Node head) {
        while (head != null) {
            System.out.print(head.data);
            if (head.next != null) System.out.print(" -> ");
            head = head.next;
        }
        System.out.println();
    }
}

Complexity Analysis

Time Complexity: O(n²) - For each node, we may scan all remaining nodes
Space Complexity: O(1) - Only using constant extra space

Optimal Approach (Reverse and Process)

Intuition

If we reverse the list, the problem becomes: remove all nodes that have a greater value on the LEFT. This can be solved in O(n) by keeping track of the maximum seen so far.

Algorithm

Reverse the linked list
Traverse from left to right, keeping track of max seen
If current node's value < max seen, delete it
Otherwise, update max and keep the node
Reverse the list back to original order

Code

java

class Node {
    int data;
    Node next;
    
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class DeleteGreaterRightOptimal {
    public static 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;
    }
    
    public static Node deleteNodesOptimal(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        // Step 1: Reverse the list
        head = reverse(head);
        
        // Step 2: Traverse and delete nodes with smaller value than max seen
        Node curr = head;
        int maxSeen = curr.data;
        
        while (curr.next != null) {
            if (curr.next.data < maxSeen) {
                // Delete the next node
                curr.next = curr.next.next;
            } else {
                // Update max and move forward
                curr = curr.next;
                maxSeen = curr.data;
            }
        }
        
        // Step 3: Reverse back to original order
        head = reverse(head);
        
        return head;
    }
    
    public static void printList(Node head) {
        while (head != null) {
            System.out.print(head.data);
            if (head.next != null) System.out.print(" -> ");
            head = head.next;
        }
        System.out.println();
    }
    
    public static Node createList(int[] arr) {
        if (arr.length == 0) return null;
        Node head = new Node(arr[0]);
        Node curr = head;
        for (int i = 1; i < arr.length; i++) {
            curr.next = new Node(arr[i]);
            curr = curr.next;
        }
        return head;
    }
    
    public static void main(String[] args) {
        int[] arr = {12, 15, 10, 11, 5, 6, 2, 3};
        Node head = createList(arr);
        
        System.out.print("Original list: ");
        printList(head);
        
        head = deleteNodesOptimal(head);
        
        System.out.print("After deletion: ");
        printList(head);
    }
}

Complexity Analysis

Time Complexity: O(n) - Three passes through the list (reverse, process, reverse)
Space Complexity: O(1) - Only using constant extra space

Alternative: Using Recursion

Code

Complexity (Recursive)

Time: O(n)
Space: O(n) for recursion stack

Key Takeaways

Reverse Technique: Reversing transforms "greater on right" to "greater on left"
Single Pass After Reverse: O(n) instead of O(n²) by tracking maximum
Monotonic Property: Result list is monotonically decreasing
Recursive Alternative: Elegant but uses O(n) stack space
The Last Node Always Stays: No nodes to its right, so it can't be deleted
Similar to Stock Span: Uses the concept of next greater element
Edge Cases: Handle single node, already sorted (increasing/decreasing) lists

Delete nodes which have a greater value on right side

Delete Nodes Which Have a Greater Value on Right Side

Problem Statement

Example

Brute Force Approach

Intuition

Algorithm

Code

Complexity Analysis

Optimal Approach (Reverse and Process)

Intuition

Algorithm

Code

Complexity Analysis

Alternative: Using Recursion

Code

Complexity (Recursive)

Key Takeaways