Example 3:

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

Note:

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

题目大意：

给定链表，返回链表每个元素之后距离最近且值更大的元素。

解题思路：

栈（Stack）

记结果数组为ans

遍历链表，用栈维护所有不小于当前元素的数字及下标。

将栈顶所有小于当前元素head.val的数字tv及下标ti弹出，令其ans[ti] = head.val

Python代码：

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

class Solution(object):
    def nextLargerNodes(self, head):
        """
        :type head: ListNode
        :rtype: List[int]
        """
        stack = []
        ans = []
        cnt = 0
        while head:
            ans.append(0)
            while stack and stack[-1][0] < head.val:
                tv, ti = stack.pop()
                ans[ti] = head.val
            stack.append((head.val, cnt))
            cnt += 1
            head = head.next
        return ans