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.
1class ListNode:
2 def __init__(self, x):
3 self.val = x
4 self.next = None
5
6class Solution:
7 def nextLargerNodes(self, head: ListNode) -> list[int]:
8 result = []
9 stack = []
10 current = head
11 index = 0
12
13 while current:
14 while stack and stack[-1][0] < current.val:
15 _, idx = stack.pop()
16 result[idx] = current.val
17 stack.append((current.val, index))
18 result.append(0)
19 current = current.next
20 index += 1
21 return resultThis Python solution makes use of a list as a makeshift stack to track indices and values. It efficiently computes the next greater nodes in linear time as it traverses the list.
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.