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;
}
};


Java

/**
* 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;
}
}