Problem statement

https://binarysearch.com/problems/Next-Greater-Element-of-a-Linked-List/

Solution

Equal to Leetcode 1019. Next Greater Node In Linked List, but need to create linked list in the end.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, head):
        nums, stack = [], []
        while head:
            nums += [head.val]
            head = head.next
            
        n = len(nums)
        result = [0]*n
        
        for i, num in enumerate(nums):
            while stack and stack[-1][1] < num:
                a, b = stack.pop()
                result[a] = num
            stack.append((i, num))

        node = h = LLNode(-1)
        for x in result:
            node.next = LLNode(x)
            node = node.next
        return h.next