Find the Next Greater Value for Each Node in a Linked List

Implement nextLargerNodes

Given the head of a singly linked list, return an array where each position holds the value of the first node further along the list that's strictly greater than the node at that position — or 0 if no such node exists. Scanning rightward from every single node, one at a time, works but revisits the same ground over and over. A monotonic stackMonotonic StackA stack that's kept in strictly increasing or decreasing order at all times, by popping off anything that would break that order before pushing a new element. Perfect for "next greater/smaller" style questions: each element is pushed once and popped at most once, so the whole scan stays O(n) even though it looks like nested loops. answers every node's question in a single left-to-right pass — each node's value gets pushed once and popped at most once.

Example 1:

Input: head = [2,1,5]

Output: [5,5,0]

Example 2:

Input: head = [2,7,4,3,5]

Output: [7,0,5,5,0]

Example 3:

Input: head = [9,4,4,9,9]

Output: [0,9,9,0,0]

+ 5 hidden test cases run on Submit.

Constraints:

  • 1 ≤ number of nodes in head ≤ 10⁴
  • 1 ≤ node value ≤ 10⁹

head =

[2, 1, 5]