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].

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

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


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


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


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


class Solution:

	def nextLargerNodes(self, head: ListNode) -> List[int]:
		if head is None:
			return []
		if head.next is None:
			return [0]
		i = head
		stack = []
		out = []
		count = 0
		while i:
			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])
			i = i.next
			count += 1
		output = [0] * count
		for (i, j) in out:
			output[i] = j
		return output


class Solution:

	def nextLargerNodes(self, head: ListNode) -> List[int]:
		stk = []
		ans = []
		i = 0
		while head:
			ans.append(0)
			stk.append((i, head.val))
			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


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]


class Solution:

	def nextLargerNodes(self, head):
		stack = []
		res = []
		vals = []
		ind = 0
		while True:
			res += [0]
			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


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]


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]


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
		while head:
			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


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


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]


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


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


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__
		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)
		while stack:
			pos = stack.pop()
			res[pos] = 0
		return res


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


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


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


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


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


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


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
		return answers


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


class Solution:

	def nextLargerNodes(self, head: ListNode) -> List[int]:
		temp = []
		i = head
		while i != None:
			temp.append(i.val)
			i = i.next
		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


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


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


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


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


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


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


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]:
					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


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


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
				elif 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


class Solution:

	def nextLargerNodes(self, head: ListNode) -> List[int]:
		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


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


class Solution:

	def nextLargerNodes(self, head: ListNode) -> List[int]:
		node = head
		ans = []
		stack = []
		i = 0
		while node is not None:
			ans.append(0)
			if len(stack):
				while len(stack) and node.val > stack[-1][1]:
					j = stack[-1][0]
					ans[j] = node.val
					stack.pop()
			stack.append((i, node.val))
			node = node.__next__
			i += 1
		return ans


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

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])]


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


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


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


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])]
		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


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


class Solution:

	def nextLargerNodes(self, head: ListNode) -> List[int]:
		stack = []
		curr = head
		while curr:
			stack.append(curr.val)
			curr = curr.__next__
		result = [0] * len(stack)
		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:
			result[stack2.pop()] = 0
		return result


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__
		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


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


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


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


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
		return res


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]


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


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


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


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__
		return res[:ind]


class Solution:

	def nextLargerNodes(self, head: ListNode) -> List[int]:
		data = []
		node = head
		maxN = 0
		while node != None:
			data.append(node.val)
			node = node.next
		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):
			maxN = max(maxN, data[i])
			if maxN != data[i]:
				out.appendleft(maxN)
			else:
				out.appendleft(0)
		return list(out)
		return out


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]


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


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]