Remove Nodes From Linked List
Mahabharata — Purging the Weak — Only Warriors With No Greater One After Them Remain
यस्य पश्चात् महाबलः न आयाति — सः स्थिरः। यस्य पश्चात् महाबलः आयाति — सः निर्गच्छेत्॥
*One for whom no mightier comes after — he stands firm. One for whom a mightier follows — he must step aside.*
The Story
Given the head of a linked list, remove all nodes that have a strictly greater value anywhere to their RIGHT. Return the modified list.
For `5→2→13→3→8`, remove 5 (13 is to its right), remove 2 (13 is to its right), remove 3 (8 is to its right). Keep 13 and 8. Result: `13→8`.
This is a direct application of the monotone stack pattern — we keep only nodes that are "greater than or equal to all that follow them."
**Stack approach — monotone decreasing stack of nodes:** - Process each node in order - While the stack's top node has a value LESS THAN the current node: pop (remove it) - Push the current node - At the end, the stack (from bottom to top) gives us the result in order
Trace `5→2→13→3→8`: - Push 5. stack=[5] - Push 2 (5>2). stack=[5,2] - 13: 2<13→pop 2. 5<13→pop 5. push 13. stack=[13] - 3: 13>3. push 3. stack=[13,3] - 8: 3<8→pop 3. 13>8. push 8. stack=[13,8] - Rebuild list from stack bottom to top: 13→8
Result: `13→8` ✓
"Each node removed was dominated by something to its right," the general noted. "The monotone decreasing stack naturally preserves only those with no greater successor."
Alternative: Reverse the list → traverse → keep only increasing values → reverse back. Same O(n) result.
The Check-Every-Right Approach
For each node, check if any node to its right has a greater value. If yes, remove it. O(n²).
public ListNode removeNodesBruteForce(ListNode head) {
ListNode dummy = new ListNode(Integer.MAX_VALUE);
dummy.next = head;
ListNode prev = dummy;
while (prev.next != null) {
ListNode curr = prev.next;
boolean dominated = false;
ListNode check = curr.next;
while (check != null) { if (check.val > curr.val) { dominated = true; break; } check = check.next; }
if (dominated) prev.next = curr.next;
else prev = curr;
}
return dummy.next;
}The Monotone Stack Node Wisdom
public ListNode removeNodes(ListNode head) {
Deque<ListNode> stack = new ArrayDeque<>();
// Build monotone decreasing stack
for (ListNode cur = head; cur != null; cur = cur.next) {
while (!stack.isEmpty() && stack.peek().val < cur.val) {
stack.pop();
}
stack.push(cur);
}
// Rebuild list from stack (bottom = first node, top = last)
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
// Stack is top-to-bottom, so collect into array and reverse
ListNode[] nodes = stack.toArray(new ListNode[0]);
for (int i = nodes.length - 1; i >= 0; i--) {
curr.next = nodes[i];
curr = curr.next;
}
curr.next = null;
return dummy.next;
}Step-by-Step Walkthrough
5→2→13→3→8: Push 5:[5] Push 2(5>2):[5,2] 13>2→pop 2. 13>5→pop 5. Push 13:[13] Push 3(13>3):[13,3] 8>3→pop 3. 8<13, stop. Push 8:[13,8] Rebuild: 13→8 ✅
Deep Insight
**Connection to st-4 (next greater element):** In st-4, we found the next greater VALUE for each element. Here, we're essentially removing elements that HAVE a next greater element. The monotone stack mechanics are identical — the difference is in what we do with the popped elements (record vs. discard).
**Alternative — reverse approach:** 1. Reverse the list 2. Traverse maintaining running max. Keep nodes >= max; update max. 3. Reverse the filtered list back. This avoids rebuilding from stack but requires two extra reversal passes.
**Stack stores nodes, not indices:** Since we need to rebuild the linked list with original node objects, we push actual ListNode references.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Check all right neighbors for each node |
| Optimal | O(n) | O(n) | Stack stores at most n nodes |
Pattern Recognition
✅ Remove nodes with greater value to their right ✅ Monotone decreasing stack of nodes ✅ Pop when current > top (popped nodes are removed) ✅ Rebuild from stack after traversal **LeetCode Trigger Phrases:** → "remove nodes from linked list" based on right-dominance → "keep only non-dominated elements" → Any "remove if greater exists to the right" problem
Bhagavad Gita 2.20
न जायते म्रियते वा कदाचिन्नायं भूत्वा भविता वा न भूयः। अजो नित्यः शाश्वतोऽयं पुराणो न हन्यते हन्यमाने शरीरे॥
The soul is never born nor dies at any time. It has not come into being, does not come into being, and will not come into being. It is unborn, eternal, ever-existing, and primeval.
Connection: The nodes that survive — those without a greater element to their right — are like eternal truths that no subsequent force can supersede. The nodes that are removed are not destroyed in any absolute sense; they simply yield to a greater force that follows them. The monotone stack performs this cosmic selection: only those elements for which nothing greater follows can claim permanence in the final formation.