Watch 10 video solutions for Next Greater Node In Linked List, a medium level problem involving Array, Linked List, Stack. This walkthrough by Nick White has 12,301 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given the head of a linked list with n nodes.
For each node in the list, find the value of the next greater node. That is, for each node, find the value of the first node that is next to it and has a strictly larger value than it.
Return an integer array answer where answer[i] is the value of the next greater node of the ith node (1-indexed). If the ith node does not have a next greater node, set answer[i] = 0.
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]
Constraints:
n.1 <= n <= 1041 <= Node.val <= 109Problem Overview: You receive the head of a singly linked list. For every node, return the value of the next node to the right that has a strictly greater value. If no such node exists, return 0 for that position. The result is returned as an array aligned with the node order.
Approach 1: Monotonic Stack with Array Conversion (O(n) time, O(n) space)
Traverse the linked list once and copy all node values into an array. This converts the problem into the classic “next greater element” problem. Iterate through the array while maintaining a monotonic stack that stores indices of elements whose next greater value hasn't been found yet. When the current value is greater than the value at the stack's top index, pop that index and set its answer to the current value. Push the current index afterward. Each index is pushed and popped at most once, which guarantees O(n) time. This is the most common and interview-friendly solution.
Approach 2: Reverse Traversal with Stack (O(n) time, O(n) space)
Instead of processing from left to right, first convert the linked list into an array, then traverse it from right to left. Maintain a stack that keeps candidate values in decreasing order. For each element, pop all stack values less than or equal to the current value since they cannot be the next greater element. The remaining top of the stack is the next greater value. Record it and push the current value onto the stack. This approach still uses a stack but avoids storing indices. Time complexity remains O(n) and space complexity is O(n) for the stack and output.
Recommended for interviews: The monotonic stack approach is what interviewers typically expect. Converting the list to an array simplifies traversal and aligns with the standard “next greater element” pattern seen in many stack-based problems. Explaining the brute-force intuition (checking each node against all future nodes) shows understanding, but implementing the monotonic stack solution demonstrates mastery of linear-time optimization.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Scan | O(n²) | O(1) | Good for explaining the basic idea or very small lists |
| Monotonic Stack with Array | O(n) | O(n) | Best general solution; standard next greater element pattern |
| Reverse Traversal with Stack | O(n) | O(n) | Useful when scanning from right and keeping decreasing stack of values |