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 <= 109This approach leverages a monotonic stack to efficiently find the next greater element for each node in the linked list. By traversing the linked list once, we can maintain a stack to track potentially greater nodes and update results as we traverse.
This C solution uses an array-based stack to capture and process nodes from the linked list. As each node is encountered, it checks the stack for any nodes smaller than the current node. If found, it updates the result set. The code is efficient and operates in O(n) time complexity.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the linked list, because each node is pushed and popped from the stack at most once.
Space Complexity: O(n), needed for storing the result and stack.
In this approach, reverse the linked list initially and then traverse, keeping track of the next greatest node using a stack. As this traversal is reversed, use a stack to efficiently find and keep the nearest greatest value.
In this approach, the linked list is reversed first. As we traverse from the new start, greater elements are stacked and compared for finding the next greater node. At the end, a final reversal of results provides the answer.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(n)
| Approach | Complexity |
|---|---|
| Monotonic Stack Approach | Time Complexity: O(n), where n is the length of the linked list, because each node is pushed and popped from the stack at most once. |
| Reverse Traversal with Stack Approach | Time Complexity: O(n) |
Next Greater Element | Two Variants | Leetcode • take U forward • 265,567 views views
Watch 9 more video solutions →Practice Next Greater Node In Linked List with our built-in code editor and test cases.
Practice on FleetCode