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