Delete Nodes with Greater on Right

Time: O(n)

Space: O(n)

Intuition

A node should be removed when some value to its right is strictly larger, so the surviving list is exactly the subsequence of nodes that are not dominated by anything on their right. Processing from right to left makes the decision local: once the suffix is already filtered, the current node stays only if it is at least as large as the suffix head.

Algorithm

1Base case: if head is null or head.next is null, return head.
2Recursively filter the suffix starting at head.next; let tp be the returned head.
3If tp.data > head.data, skip head and return tp.
4Otherwise set head.next = tp and return head.

Example Walkthrough

Input: head = 12 -> 20 -> 4 -> 15 -> 10

1.Filter suffix from 20: filtered tail becomes 20 -> 15 -> 10.
2.At 4: suffix head 20 > 4, so delete 4.
3.At 20: suffix head 15 is not greater than 20, keep 20 -> 15 -> 10.
4.At 12: suffix head 20 > 12, so delete 12.

Output: 20 -> 15 -> 10

Common Pitfalls

•Compare against the filtered suffix head, not the original next node.
•When tp.data > head.data, return tp directly; do not leave a dangling head reference.
•An iterative right-to-left pass with a running maximum also works in O(1) extra space.

Delete Nodes with Greater on Right.java

Java

// Approach: Recursively process from right to left. After fixing the suffix, drop the current node
// if the suffix head is strictly greater; otherwise keep it and link to the filtered suffix.
// Time: O(n) Space: O(n) for recursion stack

class Node {

    int data;
    Node next;

    Node(int d) {
        data = d;
        next = null;
    }
}

class Solution {

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

        Node tp = compute(head.next);

        if (tp.data > head.data) {
            return tp;
        }

        head.next = tp;

        return head;
    }
}

Was this solution helpful?