##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1019.html

# 1019. Next Greater Node In Linked List (Medium)

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

Companies:
Microsoft

Related Topics:

## Solution 1. Monostack

// OJ: https://leetcode.com/problems/next-greater-node-in-linked-list/
// Time: O(N)
// Space: O(N)
class Solution {
ListNode h;
node->next = h.next;
h.next = node;
}
return h.next;
}
public:
vector<int> ans;
stack<int> s;
while (s.size() && s.top() <= head->val) s.pop();
ans.push_back(s.size() ? s.top() : 0);
}
reverse(ans.begin(), ans.end());
return ans;
}
};


## Solution 2. Monostack

// OJ: https://leetcode.com/problems/next-greater-node-in-linked-list/
// Time: O(N)
// Space: O(N)
class Solution {
public:
vector<int> ans;
stack<int> s;
for (int i = 0; i < ans.size(); ++i) {
while (s.size() && ans[s.top()] < ans[i]) {
ans[s.top()] = ans[i];
s.pop();
}
s.push(i);
}
for (; s.size(); s.pop()) ans[s.top()] = 0;
return ans;
}
};

• /**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
Stack<ListNode> nodesStack = new Stack<ListNode>();
while (temp != null) {
nodesStack.push(temp);
temp = temp.next;
}
int length = nodesStack.size();
int[] nextLarger = new int[length];
Stack<Integer> largestStack = new Stack<Integer>();
for (int i = length - 1; i >= 0; i--) {
ListNode node = nodesStack.pop();
int value = node.val;
while (!largestStack.isEmpty() && largestStack.peek() <= value)
largestStack.pop();
if (!largestStack.isEmpty())
nextLarger[i] = largestStack.peek();
largestStack.push(value);
}
return nextLarger;
}
}

############

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
List<Integer> nums = new ArrayList<>();
}
Deque<Integer> stk = new ArrayDeque<>();
int n = nums.size();
int[] ans = new int[n];
for (int i = n - 1; i >= 0; --i) {
while (!stk.isEmpty() && stk.peek() <= nums.get(i)) {
stk.pop();
}
if (!stk.isEmpty()) {
ans[i] = stk.peek();
}
stk.push(nums.get(i));
}
return ans;
}
}

• // OJ: https://leetcode.com/problems/next-greater-node-in-linked-list/
// Time: O(N)
// Space: O(N)
class Solution {
ListNode h;
node->next = h.next;
h.next = node;
}
return h.next;
}
public:
vector<int> ans;
stack<int> s;
while (s.size() && s.top() <= head->val) s.pop();
ans.push_back(s.size() ? s.top() : 0);
}
reverse(ans.begin(), ans.end());
return ans;
}
};

• # Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
def nextLargerNodes(self, head: ListNode) -> List[int]:
nums = []
s = []
larger = [0] * len(nums)
for i, num in enumerate(nums):
while s and nums[s[-1]] < num:
larger[s.pop()] = num
s.append(i)
return larger

############

# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:rtype: List[int]
"""
nums = []
stack = []
res = [0] * len(nums)
for i, n in enumerate(nums):
while stack and nums[stack[-1]] < n:
res[stack.pop()] = n
stack.append(i)
return res

• /**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
nums := []int{}
}
stk := []int{}
n := len(nums)
ans := make([]int, n)
for i := n - 1; i >= 0; i-- {
for len(stk) > 0 && stk[len(stk)-1] <= nums[i] {
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
ans[i] = stk[len(stk)-1]
}
stk = append(stk, nums[i])
}
return ans
}

• /**
* class ListNode {
*     val: number
*     next: ListNode | null
*     constructor(val?: number, next?: ListNode | null) {
*         this.val = (val===undefined ? 0 : val)
*         this.next = (next===undefined ? null : next)
*     }
* }
*/

interface Item {
index: number;
val: number;
}

function nextLargerNodes(head: ListNode | null): number[] {
const res: number[] = [];
const stack: Item[] = [];
for (let i = 0; cur != null; i++) {
res.push(0);
const { val, next } = cur;
while (stack.length !== 0 && stack[stack.length - 1].val < val) {
res[stack.pop().index] = val;
}
stack.push({
val,
index: i,
});
cur = next;
}
return res;
}


• /**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @return {number[]}
*/
var nextLargerNodes = function (head) {
let nums = [];
}
const n = nums.length;
let larger = new Array(n).fill(0);
let stack = [];
for (let i = 0; i < n; i++) {
let num = nums[i];
while (stack.length > 0 && nums[stack[stack.length - 1]] < num) {
larger[stack.pop()] = num;
}
stack.push(i);
}
return larger;
};


• // Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
struct Item {
index: usize,
val: i32,
}

impl Solution {
pub fn next_larger_nodes(head: Option<Box<ListNode>>) -> Vec<i32> {
let mut res = Vec::new();
let mut stack: Vec<Item> = Vec::new();
for i in 0..usize::MAX {
if cur.is_none() {
break;
}
res.push(0);
let node = cur.as_ref().unwrap();
while !stack.is_empty() && stack.last().unwrap().val < node.val {
res[stack.pop().unwrap().index] = node.val;
}
stack.push(Item {
index: i,
val: node.val,
});
cur = &node.next;
}
res
}
}