LeetCode 1019: Next Greater Node In Linked List (Array Conversion + Monotonic Stack)
LeetCode 1019Linked ListMonotonic StackToday we solve LeetCode 1019 - Next Greater Node In Linked List.
Source: https://leetcode.com/problems/next-greater-node-in-linked-list/
English
Problem Summary
For every node in a singly linked list, find the value of the first node to its right with a strictly greater value. If none exists, answer 0 for that position.
Key Insight
A linked list has no random access, so we first copy values into an array. Then we use a monotonic decreasing stack of indices. When current value is greater than the value at stack top index, we resolve that index's answer with the current value.
Algorithm
- Traverse the linked list and store values in array vals.
- Create ans of same size, initialized with 0.
- Maintain a stack of indices whose next greater value is not found yet, with values in decreasing order.
- For each index i: while stack not empty and vals[i] > vals[stackTop], set ans[stackTop] = vals[i] and pop.
- Push i. Remaining indices naturally keep answer 0.
Complexity Analysis
Let n be number of nodes.
Time: O(n).
Space: O(n).
Common Pitfalls
- Trying nested scans from each node, which becomes O(n^2).
- Using a value stack instead of index stack, making updates to exact answer positions hard.
- Forgetting that equal value is not greater; condition must be strictly >.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int[] nextLargerNodes(ListNode head) {
List<Integer> vals = new ArrayList<>();
for (ListNode cur = head; cur != null; cur = cur.next) {
vals.add(cur.val);
}
int n = vals.size();
int[] ans = new int[n];
Deque<Integer> stack = new ArrayDeque<>(); // store indices
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && vals.get(i) > vals.get(stack.peek())) {
ans[stack.pop()] = vals.get(i);
}
stack.push(i);
}
return ans;
}
}func nextLargerNodes(head *ListNode) []int {
vals := []int{}
for cur := head; cur != nil; cur = cur.Next {
vals = append(vals, cur.Val)
}
n := len(vals)
ans := make([]int, n)
stack := []int{} // indices
for i := 0; i < n; i++ {
for len(stack) > 0 && vals[i] > vals[stack[len(stack)-1]] {
idx := stack[len(stack)-1]
stack = stack[:len(stack)-1]
ans[idx] = vals[i]
}
stack = append(stack, i)
}
return ans
}class Solution {
public:
vector<int> nextLargerNodes(ListNode* head) {
vector<int> vals;
for (ListNode* cur = head; cur != nullptr; cur = cur->next) {
vals.push_back(cur->val);
}
int n = vals.size();
vector<int> ans(n, 0);
vector<int> st; // indices
for (int i = 0; i < n; ++i) {
while (!st.empty() && vals[i] > vals[st.back()]) {
ans[st.back()] = vals[i];
st.pop_back();
}
st.push_back(i);
}
return ans;
}
};class Solution:
def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:
vals = []
cur = head
while cur:
vals.append(cur.val)
cur = cur.next
ans = [0] * len(vals)
stack = [] # indices
for i, v in enumerate(vals):
while stack and v > vals[stack[-1]]:
ans[stack.pop()] = v
stack.append(i)
return ansvar nextLargerNodes = function(head) {
const vals = [];
for (let cur = head; cur !== null; cur = cur.next) {
vals.push(cur.val);
}
const ans = new Array(vals.length).fill(0);
const stack = []; // indices
for (let i = 0; i < vals.length; i++) {
while (stack.length > 0 && vals[i] > vals[stack[stack.length - 1]]) {
const idx = stack.pop();
ans[idx] = vals[i];
}
stack.push(i);
}
return ans;
};中文
题目概述
对于单链表中的每个节点，找到它右侧第一个严格更大的节点值；如果不存在，当前位置答案为 0。
核心思路
链表不支持随机访问，因此先把节点值拷贝到数组。然后用“单调递减栈（存下标）”处理“下一个更大元素”。当当前值大于栈顶下标对应值时，就可以确定栈顶位置的答案。
算法步骤
- 遍历链表，得到数组 vals。
- 初始化同长度答案数组 ans，默认全 0。
- 栈中维护“尚未找到更大值”的下标，且对应值保持递减。
- 枚举每个位置 i，当 vals[i] > vals[栈顶] 时持续弹栈，并设置 ans[弹出下标] = vals[i]。
- 最后栈内剩余位置右侧都没有更大值，保持 0 即可。
复杂度分析
设节点数为 n。
时间复杂度：O(n)。
空间复杂度：O(n)。
常见陷阱
- 对每个节点都向后扫描，退化成 O(n^2)。
- 栈里只存值不存下标，导致无法回填正确位置。
- 把“严格大于”写成“大于等于”。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int[] nextLargerNodes(ListNode head) {
List<Integer> vals = new ArrayList<>();
for (ListNode cur = head; cur != null; cur = cur.next) {
vals.add(cur.val);
}
int n = vals.size();
int[] ans = new int[n];
Deque<Integer> stack = new ArrayDeque<>(); // store indices
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && vals.get(i) > vals.get(stack.peek())) {
ans[stack.pop()] = vals.get(i);
}
stack.push(i);
}
return ans;
}
}func nextLargerNodes(head *ListNode) []int {
vals := []int{}
for cur := head; cur != nil; cur = cur.Next {
vals = append(vals, cur.Val)
}
n := len(vals)
ans := make([]int, n)
stack := []int{} // indices
for i := 0; i < n; i++ {
for len(stack) > 0 && vals[i] > vals[stack[len(stack)-1]] {
idx := stack[len(stack)-1]
stack = stack[:len(stack)-1]
ans[idx] = vals[i]
}
stack = append(stack, i)
}
return ans
}class Solution {
public:
vector<int> nextLargerNodes(ListNode* head) {
vector<int> vals;
for (ListNode* cur = head; cur != nullptr; cur = cur->next) {
vals.push_back(cur->val);
}
int n = vals.size();
vector<int> ans(n, 0);
vector<int> st; // indices
for (int i = 0; i < n; ++i) {
while (!st.empty() && vals[i] > vals[st.back()]) {
ans[st.back()] = vals[i];
st.pop_back();
}
st.push_back(i);
}
return ans;
}
};class Solution:
def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:
vals = []
cur = head
while cur:
vals.append(cur.val)
cur = cur.next
ans = [0] * len(vals)
stack = [] # indices
for i, v in enumerate(vals):
while stack and v > vals[stack[-1]]:
ans[stack.pop()] = v
stack.append(i)
return ansvar nextLargerNodes = function(head) {
const vals = [];
for (let cur = head; cur !== null; cur = cur.next) {
vals.push(cur.val);
}
const ans = new Array(vals.length).fill(0);
const stack = []; // indices
for (let i = 0; i < vals.length; i++) {
while (stack.length > 0 && vals[i] > vals[stack[stack.length - 1]]) {
const idx = stack.pop();
ans[idx] = vals[i];
}
stack.push(i);
}
return ans;
};
Comments