Next greater node in linked list
November 26, 2022
linked-list stackProblem URL: Next greater node in linked list
We can use a stack to store the nodes. We will iterate over the list from the end to the beginning. We will pop the nodes from the stack until the top node is greater than the current node. We will store the value of the top node in the result array. We will push the current node to the stack. We will reverse the result array and return it.
class Solution:
def nextLargerNodes(self, head: ListNode) -> List[int]:
res, stack = [], []
while head:
while stack and stack[-1][1] < head.val:
res[stack.pop()[0]] = head.val
stack.append([len(res), head.val])
res.append(0)
head = head.next
return res
Time complexity: O(n)
, n is the length of the list
Space complexity: O(n)