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 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.