DSA problem
Next Greater Node In Linked List
You are given the head of a singly linked list with n nodes. For each node, find the value of the next node in the list that has a strictly greater value. Return an integer array answer of length n where answer[i] is the value of the next greater node after the i-th node (0-indexed), or 0 if there is no such node.
The naive approach walks the entire list once to collect values into an array, then for each index walks forward looking for the next greater value, costing O(n²) total. While simple, it is too slow for n up to 10⁴ in adversarial cases.
This is the classic "next greater element" problem with a linked-list input. The cleanest implementation converts the list to an array in a single linear pass, then runs the standard monotonic-decreasing-stack-of-indices algorithm:
- Initialise
answerwith zeros (the default for "no next greater"). - Walk the array
i = 0..n-1maintaining a stack of indices waiting for their answer. - While the stack is non-empty and
values[i] > values[stack.top], pop the topjand setanswer[j] = values[i]. - Push
i. Indices left on the stack at the end keep their default 0.
The total time is O(n) and the space is O(n) for the converted array, the stack, and the answer.
Examples
head = [2,1,5][5,5,0]head = [2,7,4,3,5][7,0,5,5,0]head = [1,7,5,1,9,2,5,1][7,9,9,9,0,5,0,0]Constraints
- The number of nodes in the list is n.
- 1 <= n <= 10^4
- 1 <= Node.val <= 10^9
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.