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.
1using System;
2using System.Collections.Generic;
3
4public class ListNode {
5 public int val;
6 public ListNode next;
7 public ListNode(int x) { val = x; }
8}
9
10public class Solution {
11 public int[] NextLargerNodes(ListNode head) {
12 List<int> result = new List<int>();
13 Stack<int[]> stack = new Stack<int[]>();
14 int index = 0;
15 ListNode current = head;
16
17 while (current != null) {
18 while (stack.Count > 0 && stack.Peek()[0] < current.val) {
19 var top = stack.Pop();
20 result[top[1]] = current.val;
21 }
22 stack.Push(new int[] {current.val, index});
23 result.Add(0);
24 current = current.next;
25 index++;
26 }
27 return result.ToArray();
28 }
29}This C# solution utilizes a List to dynamically adjust the results array. With the stack, it tracks potentially greater nodes and updates as necessary when a greater value is found.
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
The Python solution reverses the initial linked list and applies a similar stack methodology to determine the next greater nodes. Finally, it reverses the result before returning.