Next Greater Node In Linked List — Problem & Solution
Next Greater Node In Linked List solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Next Greater Node In Linked List is a medium coding problem on arrays, stack and monotonic stack, asked in Amazon and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Stack, Monotonic Stack
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the head of a singly linked list with n nodes. For each node, find the value of the first node after it whose value is strictly larger.
Return an integer array answer where answer[i] is that value for the i-th node (0-indexed), or 0 if no later node is larger.
Example 1
Input: head = [2,1,5]
Output: [5,5,0]
Explanation: Both 2 and 1 first meet 5; nothing after 5 is larger.
Example 2
Input: head = [2,7,4,3,5]
Output: [7,0,5,5,0]
Example 3
Input: head = [4,4,4]
Output: [0,0,0]
Explanation: An equal value is not larger.
Constraints
The number of nodes in the list is n1 <= n <= 10^41 <= Node.val <= 10^9
Hints for Next Greater Node In Linked List
Hint 1
Checking every later node for every node is O(n²) — too slow for 10^4 nodes in the worst case.
Hint 2
Copy the values into an array so positions can be addressed, and keep a stack of positions that are still waiting for a larger value.
Hint 3
Keep the waiting values decreasing: when a new value arrives, it is the answer for every waiting position with a smaller value — pop them and record it. Then push the new position.
How to solve Next Greater Node In Linked List
A monotonic stack: the positions still waiting for a larger value always have non-increasing values from bottom to top, so a new value resolves a run of them from the top in one go.
Approach
- Read the list into an array
vals; letanswerbenzeros. - For each index
i: while the stack is non-empty andvals[top] < vals[i], poptopand setanswer[top] = vals[i]. - Push
i. - Positions left on the stack never meet a larger value and keep their 0; return
answer.
Why it works
When vals[i] pops index j, every index between them was either popped earlier by a value ≤ vals[i]'s competitors or is still above j — in both cases no value between them exceeded vals[j] before i, otherwise j would already have been popped. So vals[i] is the first larger value after j. Each index is pushed and popped at most once.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Use strict
<when popping: an equal value does not count as larger. - Store indices, not values, on the stack — the answer is written by position.
- Values reach 10^9, which still fits in a 32-bit int; no arithmetic is done on them.
Reference solution
Python
from typing import List, Optional
def nextLargerNodes(head: Optional[ListNode]) -> List[int]:
vals = []
while head:
vals.append(head.val)
head = head.next
answer = [0] * len(vals)
stack = []
for i, v in enumerate(vals):
while stack and vals[stack[-1]] < v:
answer[stack.pop()] = v
stack.append(i)
return answerJava
public static int[] nextLargerNodes(ListNode head) {
java.util.ArrayList<Integer> vals = new java.util.ArrayList<>();
for (; head != null; head = head.next) vals.add(head.val);
int n = vals.size();
int[] answer = new int[n];
int[] stack = new int[n];
int top = 0;
for (int i = 0; i < n; i++) {
int v = vals.get(i);
while (top > 0 && vals.get(stack[top - 1]) < v) answer[stack[--top]] = v;
stack[top++] = i;
}
return answer;
}C++
vector<int> nextLargerNodes(ListNode* head) {
vector<int> vals;
for (; head; head = head->next) vals.push_back(head->val);
vector<int> answer(vals.size(), 0), stack;
for (int i = 0; i < (int) vals.size(); i++) {
while (!stack.empty() && vals[stack.back()] < vals[i]) { answer[stack.back()] = vals[i]; stack.pop_back(); }
stack.push_back(i);
}
return answer;
}JavaScript
var nextLargerNodes = function(head) {
var vals = [];
for (; head !== null; head = head.next) vals.push(head.val);
var answer = new Array(vals.length).fill(0), stack = [];
for (var i = 0; i < vals.length; i++) {
while (stack.length > 0 && vals[stack[stack.length - 1]] < vals[i]) answer[stack.pop()] = vals[i];
stack.push(i);
}
return answer;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Stack Data Structure