Sponsored
Sponsored
This 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.
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.
1function ListNode(val) {
2 this.val = val;
3 this.next = null;
4}
5
6function nextLargerNodes(head) {
7 let result = [];
8 let stack = [];
9 let current = head;
10 let index = 0;
11
12 while (current !== null) {
13 while (stack.length > 0 && stack[stack.length - 1][0] < current.val) {
14 let [value, idx] = stack.pop();
15 result[idx] = current.val;
16 }
17 stack.push([current.val, index]);
18 result.push(0);
19 current = current.next;
20 index++;
21 }
22 return result;
23}This JavaScript solution iterates over the linked list, using a stack to track and update indices whenever a greater node is found, following an O(n) approach.
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.
Time Complexity: O(n)
Space Complexity: O(n)
1
This JavaScript solution first reverses the incoming linked list, employs a stack to find the next greater nodes, and finally adjusts the result by reversing it.