Delete nodes that have a greater value on the right side

Medium

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]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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);
}