1019. Next Greater Node In Linked List #

Problem #

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

Problem Summary #

Given a linked list, find the first node after each node whose value is greater than that node’s value. If such a node cannot be found, output 0.

Solution Approach #

This problem is similar to Problems 739, 496, and 503. There are also 2 solution methods. First store the numbers in the linked list into an array, and the overall idea of the problem becomes exactly the same as Problem 739. The ordinary approach is 2 nested loops. The optimized approach is to use a monotonic stack, maintaining a monotonically decreasing stack.

Code #

package leetcode

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

// Solution 1: Monotonic stack
func nextLargerNodes(head *ListNode) []int {
	type node struct {
		index, val int
	}
	var monoStack []node
	var res []int
	for head != nil {
		for len(monoStack) > 0 && monoStack[len(monoStack)-1].val < head.Val {
			res[monoStack[len(monoStack)-1].index] = head.Val
			monoStack = monoStack[:len(monoStack)-1]
		}
		monoStack = append(monoStack, node{len(res), head.Val})
		res = append(res, 0)
		head = head.Next
	}
	return res
}