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_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]
.
Companies:
Microsoft
Related Topics:
Linked List, Stack
Solution 1. Monostack
// OJ: https://leetcode.com/problems/next-greater-node-in-linked-list/
// Time: O(N)
// Space: O(N)
class Solution {
ListNode *reverseList(ListNode *head) {
ListNode h;
while (head) {
auto node = head;
head = head->next;
node->next = h.next;
h.next = node;
}
return h.next;
}
public:
vector<int> nextLargerNodes(ListNode* head) {
vector<int> ans;
stack<int> s;
head = reverseList(head);
for (; head; head = head->next) {
while (s.size() && s.top() <= head->val) s.pop();
ans.push_back(s.size() ? s.top() : 0);
s.push(head->val);
}
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> nextLargerNodes(ListNode* head) {
vector<int> ans;
stack<int> s;
for (; head; head = head->next) ans.push_back(head->val);
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
-
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public int[] nextLargerNodes(ListNode head) { Stack<ListNode> nodesStack = new Stack<ListNode>(); ListNode temp = head; 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; } }
-
// OJ: https://leetcode.com/problems/next-greater-node-in-linked-list/ // Time: O(N) // Space: O(N) class Solution { ListNode *reverseList(ListNode *head) { ListNode h; while (head) { auto node = head; head = head->next; node->next = h.next; h.next = node; } return h.next; } public: vector<int> nextLargerNodes(ListNode* head) { vector<int> ans; stack<int> s; head = reverseList(head); for (; head; head = head->next) { while (s.size() && s.top() <= head->val) s.pop(); ans.push_back(s.size() ? s.top() : 0); s.push(head->val); } reverse(ans.begin(), ans.end()); return ans; } };
-
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def nextLargerNodes(self, head): """ :type head: ListNode :rtype: List[int] """ nums = [] while head: nums.append(head.val) head = head.next 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