[LeetCode] 1019. Next Greater Node in Linked List

 Problem : https://leetcode.com/problems/next-greater-node-in-linked-list/

Use postorder traversal and maintain a decreasing monotonic stack.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:
        result = []
        
        def postorder(node):
            if node.next:
                stack = postorder(node.next)
                while stack and stack[-1] <= node.val:
                    stack.pop()
                
                result.append(stack[-1] if stack else 0)                
                stack.append(node.val)
                
                return stack
            else:
                result.append(0)
                return [node.val]
        
        postorder(head)
        return result[::-1]

Or maintain a increasing monotonic stack which also saves the position of each smaller value.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:
        result = []
        stack = []
        
        while head:
            while stack and stack[-1][1] < head.val:
                result[stack[-1][0]] = head.val
                stack.pop()
            
            stack.append([len(result), head.val])
            result.append(0)
            
            head = head.next
        
        return result