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.
1import java.util.*;
2
3class ListNode {
4 int val;
5 ListNode next;
6 ListNode(int x) { val = x; }
7}
8
9public class Solution {
10 public int[] nextLargerNodes(ListNode head) {
11 List<Integer> result = new ArrayList<>();
12 Stack<int[]> stack = new Stack<>();
13 ListNode current = head;
14 int index = 0;
15
16 while (current != null) {
17 while (!stack.isEmpty() && stack.peek()[0] < current.val) {
18 int[] pair = stack.pop();
19 result.set(pair[1], current.val);
20 }
21 stack.push(new int[]{current.val, index});
22 result.add(0);
23 current = current.next;
24 index++;
25 }
26 return result.stream().mapToInt(i->i).toArray();
27 }
28}The Java solution uses an ArrayList for dynamic storage and a Stack to track nodes. As each node’s value is evaluated, the stack is used to find the next greater node efficiently.
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 Java implementation utilizes a list reversal to achieve efficient computation. The stack manages greater elements found, reversing and storing results before returning.