1019. Next Greater Node In Linked List

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. 1 <= node.val <= 10^9 for each node in the linked list.
  2. The given list has length in the range [0, 10000].

Rust Solution

struct Solution;
use rustgym_util::*;

impl Solution {
    fn next_larger_nodes(mut head: ListLink) -> Vec<i32> {
        let mut nodes = vec![];
        while let Some(node) = head {
            nodes.push(node.val);
            head = node.next;
        }
        let n = nodes.len();
        let mut stack: Vec<usize> = vec![];
        let mut res = vec![0; n];
        for i in 0..n {
            while let Some(j) = stack.pop() {
                if nodes[j] < nodes[i] {
                    res[j] = nodes[i];
                } else {
                    stack.push(j);
                    break;
                }
            }
            stack.push(i);
        }
        res
    }
}

#[test]
fn test() {
    let head = list!(2, 1, 5);
    let res = vec![5, 5, 0];
    assert_eq!(Solution::next_larger_nodes(head), res);
    let head = list!(2, 7, 4, 3, 5);
    let res = vec![7, 0, 5, 5, 0];
    assert_eq!(Solution::next_larger_nodes(head), res);
    let head = list!(1, 7, 5, 1, 9, 2, 5, 1);
    let res = vec![7, 9, 9, 9, 0, 5, 0, 0];
    assert_eq!(Solution::next_larger_nodes(head), res);
}

Having problems with this solution? Click here to submit an issue on github.