100. Delete Nodes Which Have a Greater Value on the Right Side

A singly linked list contains n integer values. Delete every node that has some node with a strictly greater value anywhere to its right. Print the values that remain, in their original order.

Input: The first line contains an integer n. The second line contains n space-separated integers, the linked list's values in order. Output: Print the values that remain after deletion, in their original order, space-separated.

1 <= n <= 10^5

This 'suffix maximum survives' pattern is the same underlying idea as 'Next Greater Element' from the Stack category - both rely on scanning from the right while tracking what's already confirmed to beat everything so far.

Delete every node from a linked list that has some node with a strictly bigger value somewhere to its right. Brute force: For every node, scan everything to its right directly checking for a bigger value - this costs O(n²), too slow for large lists. Optimised: Scanning from RIGHT TO LEFT while tracking a running maximum lets you decide EVERY node's fate in O(1) per node - a node survives exactly when it's at least as large as everything already confirmed to its right, computed once each in a single linear pass.

For every node, scan all nodes to its right and check if any of them has a strictly greater value; if so, mark the node for deletion. After examining every node, build the output from the unmarked ones in original order. This is correct by definition but re-scans the tail of the list for every node, making it quadratic. Time: O(n^2) Space: O(1)

Traverse the list once, maintaining a stack of nodes that are still 'candidates' for keeping. Before pushing the current node, pop and discard any nodes on top of the stack whose value is less than the current node's value (they now have a strictly greater value to their right). After processing every node, whatever remains in the stack, read from bottom to top, is the answer. This finds the result in one pass instead of quadratically, at the cost of an auxiliary stack. Time: O(n) Space: O(n)

Reverse the linked list in place, so 'greater value somewhere to the original right' becomes 'greater value somewhere already traversed.' Walk the reversed list keeping a running maximum, deleting any node whose value is less than the maximum seen so far and updating the maximum otherwise. Finally reverse the list again to restore the original order. This achieves the same one-pass-equivalent result as the stack approach but uses only pointer manipulation, no auxiliary data structure. Time: O(n) Space: O(1)

1. Scan the list from RIGHT to LEFT, keeping track of the MAXIMUM value seen so far. 2. A node SURVIVES exactly when its value is greater than or equal to that running maximum (meaning nothing further right beats it). 3. This is equivalent to keeping only the nodes that form a non-increasing 'suffix maximum' sequence.

Time: O(n) - one single right-to-left pass through the list. Space: O(1) extra space if processed via recursion or by first reversing the list; O(n) if using an explicit stack to simulate right-to-left processing on a singly linked list (which can't be walked backward directly).

n = 1 (nothing to delete), a strictly increasing list (only the last node survives), and a strictly decreasing list (every node survives).

Be ready to explain how to achieve the right-to-left scan on a SINGLY linked list (which can't be walked backward) - either by reversing the list first, processing, then reversing back, or by using recursion (which naturally unwinds right-to-left).