Remove Nodes With a Greater Value Somewhere to Their Right
Solve this Problem
Given the
head of a singly linked list, delete every node that has some node with a strictly greater value anywhere to its right, and return the head of the resulting list.
A node needs to know about every value to its right before it can decide whether to survive — information a forward-only traversal doesn't have yet when it first reaches that node. Reversing the list (the same reverse, operate, reverse backReverse, Operate, Reverse BackReversing a list turns a "look ahead" problem into a "remember what I've already seen" problem — a single running variable, updated during one forward pass, replaces what would otherwise require repeatedly looking forward from every node. pattern used earlier in this section) turns "is anything to my right bigger?" into "is anything already scanned bigger?" — a single running maximum, tracked in one forward pass.
Test Case 1:
Input:head = [5, 2, 13, 3, 8]
Output:[13, 8]
Explanation:5, 2, and 3 each have a strictly greater value somewhere to their right (13 or 8), so they're removed.
Test Case 2:
Input:head = [1, 1, 1, 1]
Output:[1, 1, 1, 1]
Explanation:"Greater" means strictly greater — equal values never cause a removal, so nothing is removed here.
Test Case 3:
Input:head = [10, 4, 3, 5]
Output:[10, 5]
Explanation:4 and 3 both have 5 to their right; 10 and 5 have nothing greater to their right, so they survive.
Constraints
- ◆
1 ≤ number of nodes in head ≤ 10⁵ - ◆
1 ≤ node value ≤ 10⁵
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
🧪Try your own test case
| 1 | class Solution { |
| 2 | public Node removeNodes(Node head) { |
| 3 | Node prev = null, curr = head; |
| 4 | while (curr != null) { |
| 5 | Node next = curr.next; |
| 6 | curr.next = prev; |
| 7 | prev = curr; |
| 8 | curr = next; |
| 9 | } |
| 10 | head = prev; |
| 11 | |
| 12 | Node node = head, prevKept = null; |
| 13 | int maxSoFar = Integer.MIN_VALUE; |
| 14 | while (node != null) { |
| 15 | if (node.val >= maxSoFar) { |
| 16 | maxSoFar = node.val; |
| 17 | prevKept = node; |
| 18 | node = node.next; |
| 19 | } else { |
| 20 | prevKept.next = node.next; |
| 21 | node = node.next; |
| 22 | } |
| 23 | } |
| 24 | |
| 25 | prev = null; curr = head; |
| 26 | while (curr != null) { |
| 27 | Node next = curr.next; |
| 28 | curr.next = prev; |
| 29 | prev = curr; |
| 30 | curr = next; |
| 31 | } |
| 32 | return prev; |
| 33 | } |
| 34 | } |
| 35 |
Linked List
null
Linked Listnull
5
curr
2
13
3
8
Variables
prev
nullcurr
5INITIALIZE
First, reverse the whole list — that turns "greater somewhere to the right" into a simple running-maximum scan.
Step 1 / 24
Approach & Solutions
Brute Force — For Each Node, Scan Rightward for a Greater Value
GoodCopy every node's value into an array, then decide each node's fate independently: for index i, scan every index to its right — if any of them holds a strictly greater value, i gets marked for removal. Once every index has been decided, rebuild the list keeping only the ones that survived.
Time
O(n²)Space
O(n)Java
1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node removeNodes(Node head) {
9 List<Integer> vals = new ArrayList<>();
10 Node curr = head;
11 while (curr != null) {
12 vals.add(curr.val);
13 curr = curr.next;
14 }
15 int n = vals.size();
16 boolean[] keep = new boolean[n];
17 for (int i = 0; i < n; i++) {
18 keep[i] = true;
19 for (int j = i + 1; j < n; j++) {
20 if (vals.get(j) > vals.get(i)) {
21 keep[i] = false;
22 break;
23 }
24 }
25 }
26 Node dummy = new Node(0);
27 Node tail = dummy;
28 for (int i = 0; i < n; i++) {
29 if (keep[i]) {
30 tail.next = new Node(vals.get(i));
31 tail = tail.next;
32 }
33 }
34 return dummy.next;
35 }
36}Optimal — Reverse, Keep While Value ≥ Running Max, Reverse Back
OptimalA node survives exactly when it's greater than or equal to everything to its right — in other words, when it's a new maximum when scanned from the right. Reverse the list so that scan becomes a simple left-to-right pass: track the running maximum, keep a node (and update the max) whenever its value is at least that maximum, and unlink it otherwise. Reverse back to restore the original order.
Time
O(n)Space
O(1)Java
1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node removeNodes(Node head) {
9 Node prev = null, curr = head;
10 while (curr != null) {
11 Node next = curr.next;
12 curr.next = prev;
13 prev = curr;
14 curr = next;
15 }
16 head = prev;
17
18 Node node = head, prevKept = null;
19 int maxSoFar = Integer.MIN_VALUE;
20 while (node != null) {
21 if (node.val >= maxSoFar) {
22 maxSoFar = node.val;
23 prevKept = node;
24 node = node.next;
25 } else {
26 prevKept.next = node.next;
27 node = node.next;
28 }
29 }
30
31 prev = null; curr = head;
32 while (curr != null) {
33 Node next = curr.next;
34 curr.next = prev;
35 prev = curr;
36 curr = next;
37 }
38 return prev;
39 }
40}