Next Greater Node In Linked List
Medium · Linked Lists · Linked List · Stack · Monotonic Stack
Problem
You are given the head of a linked list with n nodes, numbered 0 to n - 1 from the head.
Return an integer array answer of length n where answer[i] is the value of the first node after node i whose value is strictly larger than node i's value. If no later node is larger, answer[i] = 0.
Examples
Input: head = [2,7,4,3,5] Output: [7,0,5,5,0]
2 is beaten by 7; nothing after 7 is larger; 4 and 3 are both first beaten by 5.
Input: head = [6,6,1] Output: [0,0,0]
Nothing after either 6 is strictly larger, and 1 is last.
Input: head = [1,2,3] Output: [2,3,0]
Each node is beaten by its neighbor; the last has nothing after it.
Constraints
- The list has n nodes, 1 <= n <= 10^4
- 1 <= Node.val <= 10^9
Approaches
- Scan forward from every node — time O(n²), space O(1) extra
Follow-up
This is the "next greater element" pattern on a list instead of an array: the stack holds indexes because a linked list cannot be indexed, and the answer array is filled in place as nodes are settled. The same stack gives the next smaller value (flip the comparison) or the previous greater value (read the stack top before pushing).
Related problems
Start free on Cariara · Coding problems · System design studio
