We are given a linked list with head as the first node.  Let's number the nodes in the list: node_1, node_2, node_3, ... etc.
Each node may have a next larger value: for node_i, next_larger(node_i) is the node_j.val such that j > i, node_j.val > node_i.val, and j is the smallest possible choice.  If such a j does not exist, the next larger value is 0.
Return an array of integers answer, where answer[i] = next_larger(node_{i+1}).
Note that in the example inputs (not outputs) below, arrays such as [2,1,5] represent the serialization of a linked list with a head node value of 2, second node value of 1, and third node value of 5.
 

Example 1:
Input: [2,1,5]
Output: [5,5,0]


Example 2:
Input: [2,7,4,3,5]
Output: [7,0,5,5,0]


Example 3:
Input: [1,7,5,1,9,2,5,1]
Output: [7,9,9,9,0,5,0,0]

 
Note:

1 <= node.val <= 10^9 for each node in the linked list.
The given list has length in the range [0, 10000].

Difficulty: interview

Starter code:

# 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: ListNode) -> List[int]:
        

Solutions:
# 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: ListNode) -> List[int]:
        if head==None:
            return 0
        temp=head
        arr=[]
        stack=[]
        while temp:
            arr.append(temp.val)
            temp=temp.__next__
        output=[0]*len(arr)
        for i in range(len(arr)):
            while stack and arr[stack[-1]]<arr[i]:
                output[stack.pop()]=arr[i]
            stack.append(i)
        return output
        
       
            
                
                


# 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: ListNode) -> List[int]:
        cur, nodes = head, []
        while cur: 
            nodes += [cur.val] 
            cur = cur.next
        
        out = [0]*len(nodes)
        stack= []
        for i in range(len(out)):
            
            while len(stack) and nodes[stack[-1]] < nodes[i]: 
                out[stack.pop()] = nodes[i]
            stack.append(i)
        return out

# 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: ListNode) -> List[int]:
        count_list = 0
        tmp = head
        while tmp:
            count_list += 1
            tmp = tmp.next
        result = [0] * count_list
        stack = list()
        position = 0
        while head:
            while len(stack) and stack[-1][0] < head.val:
                result[stack[-1][1]] = head.val
                stack.pop()
            stack.append((head.val, position))
            position += 1
            head = head.next
        
        return result

# 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: ListNode) -> List[int]:
        
        nums=[]
        while head:
            nums.append(head.val)
            head=head.next
        map={}
        stack=[]
        for i,x in enumerate(nums):
            while stack and stack[-1][1]<x:
                map[stack.pop()[0]]=x
                
            stack.append((i,x))
        res=[]
        for i,x in enumerate(nums):
            res.append(map.setdefault(i,0))
        return res

# 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: ListNode) -> List[int]:
        # 用stack存一个递减列表，每次遇到大的数就出栈，同时更新stack中存的index对应的output
        if head is None:
          return []
        if head.next is None:
          return [0]

        i = head
        stack = []
        out = []
        count = 0
        while i:
          # print('node ', i.val)
          if not stack:
            stack.append([count, i.val])
          elif i.val <= stack[-1][1]:
            stack.append([count, i.val])
          else:
            while stack and i.val > stack[-1][1]:
              tmp_count, tmp_val = stack.pop()
              out.append([tmp_count, i.val])
            stack.append([count, i.val])
          # print(stack, out)
          i = i.next
          count += 1

        output = [0] * count
        for i, j in out:
          output[i] = j
        return output

# 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: ListNode) -> List[int]:
        stk = []
        ans = []
        i = 0
        while head:
            ans.append(0)
            stk.append((i,head.val))
            # print(i, head.val, stk)
            while head.next and stk and head.next.val>stk[-1][1]:
                j,_=stk.pop()
                ans[j]=head.next.val
            head = head.next
            i+=1
        return ans

# 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: ListNode) -> List[int]:
        stack = []
        tail = head
        res = [] 
        if not head:
            return res
        res = [None] * 10000
        idx = 0
        while tail:
            while stack and tail.val > stack[-1][0]:
                _, i = stack.pop()
                res[i] = tail.val
            if not stack or tail.val <= stack[-1][0]:
                stack.append((tail.val, idx))
            tail = tail.next
            idx += 1
        i = 0
        while i < len(stack):
            _, index = stack[i]
            res[index] = 0
            i+=1
        return res[:idx]

# 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):

        stack = []
        res = []
        vals = []

        ind = 0

        while True:

            res+=[0]

            #print(stack, vals, ind, res, head.val)
            
            while len(stack)>0 and vals[stack[-1]]<head.val:
                res[stack[-1]] = head.val
                stack.pop()
                


            stack+=[ind]
            vals+=[head.val]

            ind+=1

            
            if head.__next__ is not None:
                head = head.__next__
            else:
                break
            
        
        return res


# 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: ListNode) -> List[int]:
        if not head:
            return []
        orig_head = head
        all_res = []
        stack = []
        i = 0
        while head:
            while stack:
                v, j = stack[-1]
                if head.val > v:
                    all_res.append((head.val, j))
                    stack.pop()
                else:
                    break
            stack.append((head.val, i))
            head = head.__next__
            i += 1
        while stack:
            _, top = stack.pop()
            all_res.append((0, top))
        all_res = sorted(all_res, key=lambda x: x[1])
        return [v for v, _ in all_res]
                


# 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: ListNode) -> List[int]:
        if head is None:
            return []
        stack=[];index=0;length=0;
        ansarray=[0]*100001
        while head:
            while(len(stack) and head.val>stack[-1][0].val):
                k=stack.pop()
                ansarray[k[1]]=head.val
            stack.append([head,index])
            length+=1
            index+=1;head=head.next
        return ansarray[:length]

# 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: ListNode) -> List[int]:
        p=head
        stack=[]
        d=collections.defaultdict(deque)
        res=[]
        length=0
        
        while p:
            while stack and stack[-1]<p.val:
                val=stack.pop()
                d[val].append(p.val)
            stack.append(p.val)
            p=p.__next__
            length+=1
        #print(d,[0]*length)   
        while head:
            #print(head.val)
            if head.val in d:
                if d[head.val]:
                    res.append(d[head.val].popleft())
                else:
                    res.append(0)
            else:
                res.append(0)
            head=head.__next__
        return res
            
            
        
            
            


# 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: ListNode) -> List[int]:
        nums = []
        while head:
            nums.append(head.val)
            head = head.next
        
        n = len(nums)
        idx = [n] * n
        ans = [0] * n
        for i in reversed(range(0, n - 1, 1)):
            cur = i + 1
            while cur < n:
                if nums[cur] <= nums[i]:
                    cur = idx[cur]
                else:
                    ans[i] = nums[cur]
                    idx[i] = cur
                    break

        return ans

# 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: ListNode) -> List[int]:
        
        st = []
        ret = []
        def get_nxt_grt(cur):
            if not cur:
                return
            
            get_nxt_grt(cur.__next__)
            
            while st and st[-1] <= cur.val:
                st.pop()
            
            if not st:
                ret.append(0)
            else:
                ret.append(st[-1])
            st.append(cur.val)
            
        get_nxt_grt(head)
        return ret[::-1]
            


# 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: ListNode) -> List[int]:
        result = []
        if head == None:
            return result
        l = []
        result.append(0)
        l.append(head.val)
        head = head.next
        index = 0
        while head != None:
            index = len(l) - 1
            while index >= 0:
                if head.val > l[index]:
                    for i in range(len(result) - 1, -1, -1):
                        if result[i] == 0:
                            result[i] = head.val
                            break
                    index -= 1
                    l.pop()
                else:
                    break
            result.append(0)
            l.append(head.val)
            head = head.next
        return result

# 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: ListNode) -> List[int]:
        result = [0]
        stack = list()
        position = 0
        while head:
            while len(stack) and stack[-1][0] < head.val:
                result[stack[-1][1]] = head.val
                stack.pop()
            if len(result) <= position:
                result += [0] * (position - len(result) + 1)
            stack.append((head.val, position))
            position += 1
            head = head.next
        
        return result

# 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: ListNode) -> List[int]:
        pos = -1
        ans = []
        stack = []
        while head:
            pos += 1
            ans.append(0)
            while stack and stack[-1][1] < head.val:
                idx,_ = stack.pop()
                ans[idx] = head.val
            stack.append((pos,head.val))
            head = head.next
        return ans

# 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: ListNode) -> List[int]:
        p = head
        stack = []
        res = []
        i = 0
        
        while p:
            while stack and p.val > stack[-1][0].val:
                res[stack[-1][1]] = p.val
                stack.pop()
                
            stack.append((p,i))
            
            i += 1   
            p = p.next
            res.append(0)
                
        return res

from collections import deque
class Solution:
    def nextLargerNodes(self, head: ListNode) -> List[int]:
        res = []
        while head != None:
            res.append(head.val)
            head = head.__next__
        # monotonic decreasing stack
        stack = deque()
        for i in range(len(res)):
            while stack:
                if res[stack[-1]] < res[i]:
                    pos = stack.pop()
                    res[pos] = res[i]
                else: 
                    break
            stack.append(i)
        # the positions left in stack cannot find larger elements, and assign 0
        while stack:
            pos = stack.pop()
            res[pos] = 0
        return res

                    
                    


# 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: ListNode) -> List[int]:
        if head is None:
            return []
        
        n = 0
        cur = head
        while cur is not None:
            cur = cur.next
            n += 1
        
        cur = head
        pos = 0
        result = [0] * n
        stack = []
        
        while cur is not None:
            while stack and stack[-1][0] < cur.val:
                result[stack[-1][1]] = cur.val
                stack.pop()
            stack.append([cur.val, pos])
            
            cur = cur.next
            pos += 1
        
        return result

# 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: ListNode) -> List[int]:
        t = head
        temp = []
        while t:
            temp.append(t.val)
            t = t.next
        stack, result = [0], []
        for i in range(1, len(temp)):
            if temp[i] > temp[stack[-1]]:
                result.append(temp[i])
                stack.pop()
                while stack:
                    if temp[i] > temp[stack[-1]]:
                        result[stack[-1]] = temp[i]
                        stack.pop()
                    else:
                        break
                stack.append(i)
            else:
                stack.append(i)
                result.append(0)
        result.append(0)
        return result

# 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: ListNode) -> List[int]:
        p=head
        stack=[]
        d=collections.defaultdict(deque)
        res=[]
        length=0
        
        while p:
            while stack and stack[-1]<p.val:
                val=stack.pop()
                d[val].append(p.val)
            stack.append(p.val)
            p=p.__next__
            length+=1
        #print(d,[0]*length)   
        while head:
            print((head.val))
            if head.val in d:
                if d[head.val]:
                    res.append(d[head.val].popleft())
                else:
                    res.append(0)
            else:
                res.append(0)
            head=head.__next__
        return res
            
            
        
            
            


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def nextLargerVal(self, in_list):
        length = len(in_list)
        i = length - 1
        
        stack = []
        answer = []
        
        while i >= 0:
            if not stack:
                answer.append(0)
            elif stack and stack[-1] > in_list[i]:
                answer.append(stack[-1])
            elif stack and stack[-1] <= in_list[i]:
                while stack and stack[-1] <= in_list[i]:
                    stack.pop()
                    
                if stack:
                    answer.append(stack[-1])
                else:
                    answer.append(0)
                
                
            stack.append(in_list[i])
            i -= 1
              
        print(('Result is: {}'.format(answer[::-1])))
        return answer[::-1]
        
        
    def nextLargerNodes(self, head: ListNode) -> List[int]:
        if head is None:
            return
        if head.__next__ is None:
            return [0]
        
        temp = head
        
        input_list = []
        
        while temp:
            input_list.append(temp.val)
            temp = temp.__next__
            
        result = self.nextLargerVal(input_list)
        
        return result
        
        


from typing import List, Iterable, Iterator


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    \"\"\"
    Time: O(3n) => O(n)
    Space: O(3n) => O(n)
    \"\"\"

    def nextLargerNodes(self, head: ListNode) -> List[int]:
        result, stack = [], []
        while head:
            while stack and stack[-1][1] < head.val:
                result[stack.pop()[0]] = head.val
            stack.append((len(result), head.val))
            result.append(0)
            head = head.next

        return result


# 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: ListNode) -> List[int]:
        
        def get_length(head):
            count = 0 
            while head:
                count += 1 
                head = head.__next__ 
            return count 
        
        length = get_length(head)
        if length == 0:
            return []
        if length == 1:
            return [0]
        
        ans = [0] * length 
        heap = []
        heapify(heap)
        index = 0
        while head:
            node = head
            head = head.__next__ 
            while heap and heap[0][0] < node.val:
                out = heappop(heap)
                ans[out[1]] = node.val
            heappush(heap, (node.val, index))
            index += 1
        
        return ans


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addToHashmap(self,hashmap, key, val):
        if hashmap.get(key) is None:
            hashmap[key] = [val]
        else:
            x = hashmap[key]
            x.append(val)
            hashmap[key] = x
        
        
    def nextLargerNodes(self, head: ListNode) -> List[int]:
        stack = []
        curr = head
        new = []
        i = 0
        hashmap = {}
        while curr is not None:
            while i>0 and stack[i-1] < curr.val:
                x = stack.pop()
                self.addToHashmap(hashmap, x, curr.val)
                i-=1
            stack.append(curr.val)
            i+=1
            curr = curr.next
        temp = head
        while temp is not None:
            if hashmap.get(temp.val) is not None:
                x = hashmap.get(temp.val)
                if len(x) > 0:
                    new.append(x[0])
                    x.remove(x[0])
                else:
                    new .append(0)
            else:
                new.append(0)
            temp = temp.next 
        return new

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next


class Stack:
    def __init__(self):
        self.data = []
    
    def push(self,element):
        self.data.append(element)
    
    def pop(self):
        return self.data.pop()  
    
    def peek(self):
        return self.data[-1]
    
    def is_empty(self):
        return len(self.data) == 0
    

class Solution:
    def nextLargerNodes(self, head: ListNode) -> List[int]:
        aux = Stack()
        result = []
        
        current = head
        
        i = 0
        while current:
            result.append(0)
            if aux.is_empty() or aux.peek()[1] >= current.val:
                aux.push((i,current.val))
                current = current.next
                i += 1
                continue
            
            while (not aux.is_empty()) and (aux.peek()[1] < current.val):
                position, value = aux.pop()
                result[position] = current.val
            aux.push((i,current.val))
            i += 1
            current = current.next
        return result

# 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: ListNode) -> List[int]:
        numbers = []
        answers = []

        while head:
            numbers.append(head.val)
            answers.append(0)
            head = head.next
            
            n = len(numbers) - 1
            
            while head and n >= 0 and head.val > numbers[n]:
                if answers[n] == 0:
                    answers[n] = head.val
                n-=1
            # print(numbers, answers)
        return answers

# 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: ListNode) -> List[int]:
        res, stack = [], []

        while head:
            while stack and stack[-1][1] < head.val:
                top = stack.pop()
                res[top[0]] = head.val
            stack.append([len(res), head.val])
            res.append(0)
            head = head.__next__

        return res


# 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: ListNode) -> List[int]:
        temp=[]
        i=head
        while i!=None:
            temp.append(i.val)
            i=i.next
        #print(temp)
        n=len(temp)
        res=[0]*n
        for i in range(n-2,-1,-1):
            for j in range(i+1,n):
                if(temp[j]>temp[i]):
                    res[i]=temp[j]
                    break
                elif((temp[j]==temp[i])or(res[j]==0)):
                    res[i]=res[j]
                    break
        return res

# 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):
        \"\"\"
        :type head: ListNode
        :rtype: List[int]
        \"\"\"
        answer_array = []
        stack = []
        index = 0
        
        while head is not None:
            answer_array.append(0)
            current_value = head.val
            
            while stack and stack[-1][0] < current_value:
                last_value = stack.pop()
                answer_array[last_value[1]] = current_value

            stack.append((current_value, index))
            index += 1
            head = head.next

        return answer_array
            
        


# 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: ListNode) -> List[int]:
        stack = []
        count = 0
        out = []
        
        while head:
            
            out.append(0)
            while stack and head.val > stack[-1][0]:
                out[stack[-1][1]] = head.val
                stack.pop()
            stack.append((head.val,count))
            count += 1
            head = head.__next__
       
        return out
                
                


# 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: ListNode) -> List[int]:
        res = []
        i = 0
        prev_min = sys.maxsize
        val = set()
        curr = head
        while curr != None:
            n = curr.val
            if n > prev_min:
                to_remove = []
                for node in val:
                    if node[1] < n:
                        res[node[0]] = n
                        to_remove.append(node)
                for node in to_remove:
                    val.remove(node)
            else:
                prev_min = n
            val.add((i, n))
            res.append(0)
            curr = curr.__next__
            i+=1
        return res


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def __init__(self):
        self.result = []
        self.stack = []
    
    def nextLargerNodes(self, head: ListNode) -> list:
        self.__recursive(head)
        return self.result[::-1]
        
    def __recursive(self, head: ListNode) -> None:
        if head == None:
            return
        
        self.__recursive(head.__next__)
        
        val = 0
        while len(self.stack) != 0:
            val = self.stack.pop()
            
            if val > head.val:
                self.result.append(val)
                self.stack.extend([val, head.val])
                break
        
        if len(self.stack) == 0:
            self.result.append(0)
            self.stack.append(head.val)
            
        return



# 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: ListNode) -> List[int]:
        if not head:
            return [0]
        
        idx = -1
        res = []
        stack = []
        
        while head:
            res.append(0)
            
            while stack and stack[-1][1] < head.val:
                position , _ = stack.pop()
                res[position] = head.val
            
            idx += 1
            stack.append((idx , head.val))
            head = head.__next__
            
        return res
        
        


# 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: ListNode) -> List[int]:
        stack = []
        res = []
        pos = 0
        while head:
            res.append(0)
            while stack and head.val > stack[-1][1]:
                idx, _ = stack.pop()
                res[idx] = head.val
            stack.append((pos, head.val))
            pos += 1
            head = head.next
        while stack:
            idx, _ = stack.pop()
            res[idx] = 0
        return res

# 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: ListNode) -> List[int]:
        return self.stacksol(head)
        \"\"\"
        1) Go backwards
        2) Keep sorted list of numbers
        3) Upon new number, insert into list in sorted order, and remove all values smaller than that number
            a) if new number is at the end of the list (max), then return 0 for that value
            b) else, return the next larger value in the list
        \"\"\"
        vals = [] #list form of linked list
        while(head):
            vals += [head.val]
            head = head.next
        
        slist = [] #sorted max list
        alist = [] #answer
        
        for i,val in enumerate(vals[::-1]):
            newind = bisect.bisect_right(slist, val)
            slist.insert(newind, val)
            if slist[-1] == val:
                alist += [0]
            else:
                alist += [slist[newind+1]]
            slist = slist[newind:]
            
        return alist[::-1]
    
    def stacksol(self, head: ListNode) -> List[int]:
        \"\"\"
        add numbers to stack
        1) pop off all numbers lower than number first
        2) add number to answer list, in equal number of pops (else add 0 place holder)
        3) 
        
        \"\"\"
        ret, stack = [], []
        
        while(head):
            while(stack and stack[-1][0] < head.val):
                p = stack.pop()
                ret[p[1]] = head.val
            stack += [(head.val, len(ret) )]
            ret += [0]
            head = head.next
        return ret
    
    
#         ret, stack = [], []
#         while(head):
#             counter = 0
#             while(stack and stack[-1] < head.val):
#                 stack.pop()
#                 counter += 1
#             stack += [head.val]

#             for i in range(counter):
#                 ret[-(i+1)] = head.val
#             ret += [0]
#             head = head.next
#         return ret

# 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: ListNode) -> List[int]:
        p = head
        stack = []
        res = []
        i = 0
        
        while p:
            while stack and p.val > stack[-1][0].val:
                # res.append(p.val)
                res[stack[-1][1]] = p.val
                stack.pop()
                
            stack.append((p,i))
            
            i += 1   
            p = p.next
            res.append(0)
                
        return res

# 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: ListNode) -> List[int]:
        ans = []
        stack = []

        while head:
            while stack and stack[-1][0]<head.val:
                ans[stack.pop()[1]] = head.val
            stack.append((head.val, len(ans)))
            ans.append(0)
            head = head.next
        return ans

# 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: ListNode) -> List[int]:
        nums = []
        p = head
        while p:
            nums.append(p.val)
            p = p.__next__
        
        st = []
        ans = [0]* len(nums)
        for i in range(len(nums)):
            while st and nums[st[-1]] < nums[i]:
                ans[st[-1]] = nums[i]
                st.pop()
            st.append(i)
        
         
        return ans
                    

            
                
        
            


# 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: ListNode) -> List[int]:
        
    
        stack = []
        result = []
        index = 0
        while(head):
            
            if len(stack) > 0:
                if head.val > stack[-1][0]:
                    # Pop the stack, change the list
                    for i in range(len(stack)):
                        if stack[-1][0] < head.val:
                            result[stack.pop()[1]] = head.val
                    
            stack.append((head.val, index))

            result.append(0)
            index += 1
            head = head.__next__
            
            
        return result
        
            
        


# 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: ListNode) -> List[int]:
        maps = defaultdict(lambda:[]); lst = []; runner = head; 
    
        while runner:
            lst.append(runner.val)
            runner = runner.__next__
        
        for i, v in enumerate(lst): maps[v].append(i)

        res = [0 for _ in range(len(lst))]; heap = []
        for i in range(len(lst)):
            while heap and lst[i] > heap[0][0]:
                pop = heapq.heappop(heap)
                res[pop[1]] = lst[i]
            heapq.heappush(heap, (lst[i], i))
        return res
        
        


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    
    def find_best(self, head):
        current = head
        while current.next:
            if current.next.val>head.val:
                return current.next.val
            current = current.next
        return 0
    
    def nextLargerNodes(self, head: ListNode) -> List[int]:
        self.lst = []
        def helper(head, i):
            if not head:
                return
            self.lst.append(0)
            helper(head.next, i+1)
            if head.next:
                if head.next.val>head.val:
                    self.lst[i] = head.next.val
                else:
                    if self.lst[i+1] == 0 or self.lst[i+1] > head.val:
                        self.lst[i] = self.lst[i+1]
                    else:
                        self.lst[i] = self.find_best(head)
        helper(head,0)
        return self.lst

# 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: ListNode) -> List[int]:
        ##转化成stack 来做
        if not head:
            return head
        val_list = []
        while head:
            val_list.append(head.val)
            head = head.__next__
        stack = []
        res = [0 for _ in range(len(val_list))]
        for i in range(len(val_list)):
            while stack and val_list[stack[-1]] < val_list[i]:
                res[stack.pop()] = val_list[i]
            stack.append(i)
        return res

    
    
            
            


# 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: ListNode) -> List[int]:
        
    
        stack = []
        result = []
        index = 0
        while(head):
            
            if len(stack) > 0:
                if head.val > stack[-1][0]:
                    # Pop the stack, change the list
                    for i in range(len(stack)):
                        stack_val = stack.pop()
                        if stack_val[0] < head.val:
                            result[stack_val[1]] = head.val
                        else:
                            stack.append(stack_val)
            stack.append((head.val, index))

            result.append(0)
            index += 1
            head = head.__next__
            
            
        return result
        
            
        


# 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: ListNode) -> List[int]:
        stack = []
        
        current = head
        ret = []
        index = 0
        while current is not None:
            ret.append(0)
            while stack and current.val > stack[-1][1]:
                i, _ = stack.pop()
                ret[i] = current.val
            
            stack.append((index, current.val))
            
            index += 1
            current = current.next
            
        return ret

# 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: ListNode) -> List[int]:
        node = head
        ans = []
        stack = []
        i = 0
        while node is not None:
            # print(i, stack, ans)
            ans.append(0)
            if len(stack):
                while len(stack) and node.val > stack[-1][1]:
                    j = stack[-1][0]
                    ans[j] = node.val
                    # print(j, ans[j])
                    stack.pop()
            stack.append((i, node.val))
            node = node.__next__
            i += 1
        return ans


# 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: ListNode) -> List[int]:
        dic={}
        stack=[]
        i=0
        ans=[0]*100001
        while head:
            while stack and dic[stack[-1]]<head.val:
                t=stack.pop()
                ans[t]=head.val
            dic[i]=head.val
            stack.append(i)
            i+=1
            head=head.__next__
        while stack:
            t=stack.pop()
            ans[t]=0
        return ans[:i]



import heapq
# 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: ListNode) -> List[int]:
        if not head:
            return []
        
        h = []
        res = {}
        cur = head
        i = 0
        while cur:
            if len(h) == 0:
                heappush(h, (cur.val, i))
            else:
                while h and cur.val > h[0][0]:
                    val, index = heappop(h)
                    res[index] = cur.val
                heappush(h, (cur.val, i))    
            i += 1     
            cur = cur.next
        while h:
            val, index = h.pop()
            print(val, index)
            res[index] = 0
        
        return [res[index] for index in sorted([k for k in res])]

# 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: ListNode) -> List[int]:
        if not head:return []
        ans=[]
        while head:
            ans.append(head.val)
            head=head.next
        n=len(ans)
        lst=[]
        for i in range(n-1,-1,-1):
            v=ans[i]
            while lst and lst[-1]<=v:
                lst.pop()
            ans[i]=0 if not lst else lst[-1]
            lst.append(v)
        return ans

# 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: ListNode) -> List[int]:
        arr=[]
        temp = head
        while temp:
            arr.append(temp.val)
            temp = temp.next
        stk = []
        i=0
        while i<len(arr):
            while stk and arr[stk[-1]] < arr[i]:
                arr[stk.pop()] = arr[i]
            stk.append(i)
            i+=1
        while stk:
            arr[stk.pop()] = 0
        return arr       

# 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: ListNode) -> List[int]:
        if not head:
            return []
        
        stack = []
        res = []
        
        idx = 0
        while head:
            while stack and stack[-1][1] < head.val:
                pos, _ = stack.pop()
                res[pos] = head.val
            stack.append((idx, head.val))
            res.append(0)
            idx += 1
            head = head.next
        
        return res

# 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: ListNode) -> List[int]:
        arr=[]
        cur=head
        while cur:
            arr.append(cur.val)
            cur=cur.next
        st,res=[],[0]*len(arr)
        for i in range(len(arr)):
            while st and arr[i]>arr[st[-1]]:
                res[st.pop()]=arr[i]
            st.append(i)
        return res

# 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: ListNode) -> List[int]:
        vals = []
        node = head
        while node:
            vals.append(node.val)
            node = node.__next__
        
        n = len(vals)
        ret = [0 for _ in range(n)]
        q = [(n - 1, vals[n - 1])]  # idx, val

        for i in range(n - 1, -1, -1):
            curr = vals[i]
            while q:
                if q[0][1] > curr:
                    ret[i] = q[0][1]
                    heapq.heappush(q, (i, curr))
                    break
                else:
                    heapq.heappop(q)
            else:
                heapq.heappush(q, (i, curr))
        
        return ret


# 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: ListNode) -> List[int]:
        output = []
        stack = []
        curr = head
        
        while curr:
            while stack and stack[-1][1] < curr.val:
                output[stack.pop()[0]] = curr.val
            stack.append([len(output), curr.val])
            output.append(0)
            curr = curr.__next__
        return output
            

            


# 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: ListNode) -> List[int]:
        ######################################################################
       # solution 1, using stack 
        stack = []
        curr = head 
        while curr:
            stack.append(curr.val)
            curr = curr.__next__ 
            
        result = [0]* len(stack) # populate 
        stack2 = []
        
        for  i in range(len(stack)):
            while stack2 and stack[stack2[-1]] < stack[i]:
                  result[stack2.pop()] = stack[i]
            stack2.append(i)
            
        while stack2: # reaplce the indexes of the stack with 0s
            result[stack2.pop()] = 0
            
        return result
    ######################################################################
        # solution 2, using stack with two for loops 
#         output = []
#         if head.next == None:
#             return output + [0]  
#         curr = head 
#         stack = []
#         while curr:
#             stack.append(curr.val)
#             curr = curr.next 
            
#         for i in range(len(stack)-1):
#             flag = True
#             for j in range(i, len(stack)):
#                 if stack[i] < stack[j]:
#                     output.append(stack[j])
#                     flag = False 
#                     break 
#             if flag:
#                 output.append(0)
#         return output + [0]
        ######################################################################


# 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: ListNode) -> List[int]:
        results = {}
        stack = deque()
        next = head.__next__
        curr = head
        extra_values = 0
        stack.append((0, curr.val))
        index = 0
        while(next != None):
            while(len(stack) != 0 and stack[-1][1] < next.val):
                (ind, val) = stack.pop()
                print((ind, val))
                results[ind] = next.val
            index += 1
            stack.append((index, next.val))
            next = next.__next__
        #add extra zeros
        for i in range(len(stack)):
            results[stack[i][0]] = 0
        result_arr = [0] * len(results)
        for j in range(len(result_arr)):
            result_arr[j] =results[j]

        return result_arr


# 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: ListNode) -> List[int]:
        stk, res = [], []
        while head:
            while stk and head.val > stk[-1][1]:
                idx = stk.pop()[0]
                res[idx] = head.val
            stk.append([len(res), head.val])
            res.append(0)
            head = head.__next__
        return res


# 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: ListNode) -> List[int]:
        arr = []
        ptr = head
        while ptr:
            arr.append(ptr.val)
            ptr = ptr.__next__
        result = [0] * len(arr)
        s = []
        for i in range(len(arr)-1,-1,-1):
            while (len(s)>0 and s[-1]<= arr[i]):
                s.pop()
            result[i] = 0 if len(s)==0 else s[-1]
            s.append(arr[i])
        return result
            


import heapq

# 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: ListNode) -> List[int]:
        h = []
        vals = {}
        cur = head
        idx = 0
        while cur:
            while len(h) > 0 and h[0][0] < cur.val:
                print(f\"{h[0]} < {cur.val}\")
                _, i = heapq.heappop(h)
                vals[i] = cur.val
            heapq.heappush(h, (cur.val, idx))
            cur = cur.next
            idx += 1
        
        res = []
        i = 0
        while head:
            res.append(vals.get(i, 0))
            head = head.next
            i += 1
        return res
        
            
        

# 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: ListNode) -> List[int]:
        vals = []
        stack = []
        node = head
        
        while node != None:
            vals.append(node.val)
            node = node.__next__
            
        if len(vals) == 1:
            return [0]
        if len(vals) == 0:
            return 0
        
        res = [0 for _ in range(len(vals))]
        
        for i,val in enumerate(vals):
            while stack:
                if vals[stack[-1]] < val:
                    pos = stack.pop()
                    res[pos] = val
                else:
                    break
                
            stack.append(i)
            
        while stack:
            pos = stack.pop()
            res[pos] = 0
        return res
        


# 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: ListNode) -> List[int]:
        nodes = []
        curr = head
        while curr: 
            nodes.append(curr.val)
            curr = curr.next
        res = [0]*len(nodes)
        stack = []
        
        for i in range(len(nodes)): 
            while stack and nodes[stack[-1]]<nodes[i]: 
                res[stack.pop()] = nodes[i]
            
            stack.append(i)
        
        return res

# 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: ListNode) -> List[int]:
        curr = head
        i = 0
        res = []
        stack = []
        while curr:
            res.append(0)
            val = curr.val
            while stack and stack[-1][0] < val:
                v , index = stack.pop()
                res[index] = val
            
            stack.append((val,i))
            i  = i + 1
            curr = curr.__next__
        del stack    
        #print(stack)    
        return res     
        
                
                              
        


# 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: ListNode) -> List[int]:
        curr=head
        prev=None
        while curr!=None:
            temp=curr.__next__
            curr.next=prev
            prev=curr
            curr=temp
        curr=prev
        stack=[0]
        l=[]
        while curr!=None:
            if stack[-1]>curr.val:
                l.append(stack[-1])
            else:
                while stack[-1]<=curr.val and stack[-1]!=0:
                    stack.pop()
                l.append(stack[-1])
            stack.append(curr.val)
            curr=curr.__next__
        return l[::-1]
        
            


# 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: ListNode) -> List[int]:
        \"\"\"
        1) Go backwards
        2) Keep sorted list of numbers
        3) Upon new number, insert into list in sorted order, and remove all values smaller than that number
            a) if new number is at the end of the list (max), then return 0 for that value
            b) else, return the next larger value in the list
        \"\"\"
        vals = [] #list form of linked list
        while(head):
            vals += [head.val]
            head = head.next
        
        slist = [] #sorted max list
        alist = [] #answer
        
        for i,val in enumerate(vals[::-1]):
            newind = bisect.bisect_right(slist, val)
            slist.insert(newind, val)
            if slist[-1] == val:
                alist += [0]
            else:
                alist += [slist[newind+1]]
            slist = slist[newind:]
            
        return alist[::-1]

class Stack:
    def __init__(self):
        self.items = []
        self.time_stamps = dict()
        self.t = 0

    def isEmpty(self):
        return self.items == []

    def push(self, item):
        
        self.items.append([item, self.t])
        self.time_stamps[item] =self.t 
        self.t +=1
        

    def pop(self):
        return self.items.pop()

    def peek1(self):
        return self.items[len(self.items)-1][0]
    def peek2(self):
        return self.items[len(self.items)-1][1]

    def size(self):
        return len(self.items)
    def ret(self):
        return self.items





class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def nextLargerNodes(self, head: ListNode) -> List[int]:
        
        T= []
        while head:
            T.append(head.val)
            head = head.__next__
        
        def dailyTemperatures(T: List[int]) -> List[int]:
            if len(T) == 0:
                return [0]
            ans = [0]*len(T)
            stack = Stack()
            stack.push(T[0])

            for i in range(1, len(T)):
                current = T[i]
                if current <= stack.peek1():
                    stack.push(current)
                    
                else:
                    while(stack.size() !=0 and current > stack.peek1()):
                        ans[stack.peek2()] = stack.t - stack.peek2()
                        stack.pop()
                    stack.push(current)


            return ans
        S = dailyTemperatures(T)
        n = len(S)
        ans = [0]*n
        for i in range(n):
            if S[i] !=0:
                ans[i]= T[i+S[i]]
        
        return ans




# 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: ListNode) -> List[int]:
        result = [] 
        stack = []
        idx = 0
        while head:
            while stack and head.val > stack[-1][0]:
                result[stack.pop()[1]] = head.val
            stack.append((head.val, idx))                            
            result.append(0)
            head = head.__next__
            idx += 1
        return result


# 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: ListNode) -> List[int]:
        stack = []
        answer = []
        index = 0
        while head:
            answer.append(0)
            while len(stack) > 0 and stack[-1][0] < head.val:
                number_and_index = stack.pop()                
                answer[number_and_index[1]] = head.val
            stack.append((head.val, index))
            index += 1
            head = head.next
        return answer

# 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: ListNode) -> List[int]:
        return self.stacksol(head)
        \"\"\"
        1) Go backwards
        2) Keep sorted list of numbers
        3) Upon new number, insert into list in sorted order, and remove all values smaller than that number
            a) if new number is at the end of the list (max), then return 0 for that value
            b) else, return the next larger value in the list
        \"\"\"
        vals = [] #list form of linked list
        while(head):
            vals += [head.val]
            head = head.next
        
        slist = [] #sorted max list
        alist = [] #answer
        
        for i,val in enumerate(vals[::-1]):
            newind = bisect.bisect_right(slist, val)
            slist.insert(newind, val)
            if slist[-1] == val:
                alist += [0]
            else:
                alist += [slist[newind+1]]
            slist = slist[newind:]
            
        return alist[::-1]
    
    def stacksol(self, head: ListNode) -> List[int]:
        \"\"\"
        add numbers to stack
        1) pop off all numbers lower than number first
        2) add number to answer list, in equal number of pops (else add 0 place holder)
        3) 
        
        \"\"\"
        ret, stack = [], []
        
        while(head):
            while(stack and stack[-1][0] < head.val):
                p = stack.pop()
                ret[p[1]] = head.val
            stack += [(head.val, len(ret) )]

            ret += [0]
            head = head.next
        return ret
    
    
#         ret, stack = [], []
#         while(head):
#             counter = 0
#             while(stack and stack[-1] < head.val):
#                 stack.pop()
#                 counter += 1
#             stack += [head.val]

#             for i in range(counter):
#                 ret[-(i+1)] = head.val
#             ret += [0]
#             head = head.next
#         return ret

# 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: ListNode) -> List[int]:
        stack = []
        cur = head
        res = [0]*1000000
        ind = 0 

        while cur:

            while stack and stack[-1][1]< cur.val:
                res[stack[-1][0]] = cur.val
                stack.pop()


            stack.append((ind,cur.val))
            ind+=1
            cur = cur.__next__
            
        # while stack:
        #     res[stack[-1][0]] = 0
        #     stack.pop()

        return res[:ind]


# 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: ListNode) -> List[int]:
        data=[]
        node=head
        maxN=0
        while node!=None:
            data.append(node.val)
            node=node.next
      #  print(data)
        s=[]
        out=[0]*len(data)
        for i in range(len(data)-1,-1,-1):
            
            while len(s)>0 and s[-1]<=data[i]:
                s.pop()
            if len(s)>0:
                out[i]=s[-1]
            s.append(data[i])
            
        return out
        out=[]
        for i in range(len(data)-1,-1,-1):
         #   print(maxN)
            
            maxN=max(maxN,data[i])
            if maxN!=data[i]:
                out.appendleft(maxN)
            else:
                out.appendleft(0)
          #  print(data[i],maxN)
        return list(out)
        return out

# 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: ListNode) -> List[int]:
        ans, stack = [], []
        while head:
            while stack and stack[-1][1] < head.val:
                ans[stack.pop()[0]] = head.val
            stack.append([len(ans), head.val])
            ans.append(0)
            head = head.next
        return ans

# 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: ListNode) -> List[int]:
        def lreverse(head):
            if head is None:
                return head
            p = None
            q = head
            r = head.__next__
            while q:
                q.next = p
                p = q
                q = r
                if r:
                    r = r.__next__
            return p
        head = lreverse(head)
        q, res = [],[]
        while head:
            while q and head.val >= q[-1]:
                q.pop()
            if len(q) == 0:
                res.append(0)
            else:
                res.append(q[-1])
            q.append(head.val)
            head = head.__next__
            
        return res[::-1] 


# 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: ListNode) -> List[int]:
        
        memo = {}
        t=head
        nodes=[]
        while t:
            nodes.append(t.val)
            t=t.__next__
        
        maxes = [0]*len(nodes)
        sol = [0]*len(nodes)
        for idx,val in enumerate(nodes[::-1]):
            if idx != 0:
                maxes[-idx-1] = max(maxes[-idx],nodes[-idx])
            else:
                maxes[-idx-1] = nodes[-idx-1]
                
        for idx,val in enumerate(nodes):
            if val in memo and memo[val] > idx:
                sol[idx] = nodes[memo[val]]
            elif maxes[idx] > val:
                for j in range(idx+1,len(nodes)):
                    if nodes[j]>val:
                        memo[val] = j
                        sol[idx] = nodes[j]
                        break
            else:
                continue
        
        return sol


# 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: ListNode) -> List[int]:
        
        \"\"\"
        这道题分析一下其实不难，比较容易意识到需要用heap
        对于当前posi, 它应该pop heap中比它小的所有pending，然后自己进heap  
        如果最后还没出heap那就是在其后没找到比自己大的
        \"\"\"
        
        def get_length(head):
            count = 0 
            while head:
                count += 1 
                head = head.next 
            return count 
        
        length = get_length(head)
        if length == 0:
            return []
        if length == 1:
            return [0]
        
        ans = [0] * length 
        heap = []
        heapify(heap)
        index = 0
        while head:
            node = head
            head = head.next 
            while heap and heap[0][0] < node.val:
                out = heappop(heap)
                ans[out[1]] = node.val
            heappush(heap, (node.val, index))
            index += 1
        
        return ans


# 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: ListNode) -> List[int]:
        stack=[]
        res=[]
        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

# 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: ListNode) -> List[int]:
        # 借鉴自 discuss
        pos = 0
        ans = []
        stack = []  # 单调栈（递减）
        while head:
            ans.append(0)
            # 退栈的时候更新 ans 数组
            while stack and stack[-1][1] < head.val:
                idx, _ = stack.pop()
                ans[idx] = head.val
            
            stack.append((pos, head.val))
            head = head.next
            pos += 1

        return ans

# 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: ListNode) -> List[int]:
        st1 = []
        ptr = head
        while ptr:
            st1.append(ptr.val)
            ptr=ptr.__next__
        
        st2=[]
        ans=[]
        while st1:
            while st2 and st2[-1]<=st1[-1]:
                st2.pop()
            if len(st2)==0:
                ans.append(0)
            else:
                ans.append(st2[-1])
            st2.append(st1.pop())
        return ans[::-1]