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 public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
private ListNode ReverseList(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
public int[] NextLargerNodes(ListNode head) {
head = ReverseList(head);
Stack<int> stack = new Stack<int>();
List<int> result = new List<int>();
while (head != null) {
while (stack.Count > 0 && stack.Peek() <= head.val)
stack.Pop();
result.Add(stack.Count == 0 ? 0 : stack.Peek());
stack.Push(head.val);
head = head.next;
}
result.Reverse();
return result.ToArray();
}
}This C# solution illustrates reversing the list and using a stack to manage and track next greater nodes. After solving, it reverses results for output.