Description
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.
给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为：node_1, node_2, node_3, … 。
每个节点都可能有下一个更大值（next larger value）：对于 node_i，如果其 next_larger(node_i) 是 node_j.val，那么就有 j > i 且 node_j.val > node_i.val，而 j 是可能的选项中最小的那个。如果不存在这样的 j，那么下一个更大值为 0 。
返回整数答案数组 answer，其中 answer[i] = next_larger(node_{i+1}) 。
注意：在下面的示例中，诸如 [2,1,5] 这样的输入（不是输出）是链表的序列化表示，其头节点的值为 2，第二个节点值为 1，第三个节点值为 5 。
题目链接：https://leetcode.com/problems/next-greater-node-in-linked-list/
Difficulty: medium
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].
分析
- 用index模拟栈存储遍历链表的结果，每一项包含（每个节点val，在链表中的位置pos）；
- li存储每个节点对应的下一个更大值，初始为0；
- 遍历链表，若当前head的值大于栈顶元素的val，则当前栈顶元素对应节点的下一个最大节点值为head的val，修改li；
- 反之，head的val及其对应的pos入站；
- 直至遍历完链表，返回li。
参考代码
#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):
h=head
length=0
while(h!=None):
length+=1
h=h.next
if(length==0):
return []
li=[0]*length
index=[]
pos=0
while head != None:
if(len(index)!=0 and index[-1][0] < head.val):
li[index[-1][1]]=head.val
index=index[:-1]
else:
index.append((head.val,pos))
head=head.next
pos+=1
return li