Remove Nodes With a Greater Value Somewhere to Their Right

Implement removeNodes

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.

Example 1:

Input: head = [5,2,13,3,8]

Output: [13,8]

Example 2:

Input: head = [1,1,1,1]

Output: [1,1,1,1]

Example 3:

Input: head = [10,4,3,5]

Output: [10,5]

+ 5 hidden test cases run on Submit.

Constraints:

  • 1 ≤ number of nodes in head ≤ 10⁵
  • 1 ≤ node value ≤ 10⁵

head =

[5, 2, 13, 3, 8]