Delete nodes that have a greater value on the right side
Problem
Delete every node that has some node with a greater value anywhere to its right. Return the resulting list.
Example 1
Input: 12 → 15 → 10 → 11 → 5 → 6 → 2 → 3 Output: 15 → 11 → 6 → 3
Also asked as: Delete nodes which have a greater value on right side
Test cases
Case 1
Input: [12,15,10,11,5,6,2,3] Expected: [15,11,6,3]
Case 2
Input: [10,20,30,40,50,60] Expected: [60]
Case 3
Input: [60,50,40] Expected: [60,50,40]
Case 4
Input: [5] Expected: [5]
View solutionHide solution1 approach
1. Reverse, keep a running max, reverse back
Time O(n)Space O(1)
After reversing, sweep once keeping the max seen so far; drop any node smaller than that max. Reverse again.
function deleteSmallerOnRight(head) { const rev = (h) => { let p = null; while (h) { const n = h.next; h.next = p; p = h; h = n; } return p; }; head = rev(head); let maxSoFar = head, cur = head; while (cur && cur.next) { if (cur.next.val < maxSoFar.val) cur.next = cur.next.next; else { cur = cur.next; maxSoFar = cur; } } return rev(head);}