Next Greater Node In Linked List solution and explanation
Google
9 more videos on this problem
LeetCode Next Greater Node In Linked List Solution Explained - JavaNick White · 7:02 · 12K views
Find Next Greater node in a Linked List | Leetcode medium difficulty problem | 1019Code Refer · 8:00 · 4K views
LeetCode 1019 | Next Greater Node in Linked List | Day 73 | 100 Days LeetCode ChallengeedSlash · 26:08 · 2K views
Leetcode 1019 - Next Greater Node In Linked List (JAVA Solution Explained!)LC Bear · 7:29 · 1K views
Next Greater Node In Linked List | LeetCodeKnowledge Amplifier · 9:01 · 1K views
1019. Next Greater Node In Linked List | Leetcode | PythonAbdullah Arshed · 7:21 · 362 views
Leetcode-1019 : Next Greater Node in Linked List (Unexecuted Jobs Model)Kumar Sanjeev · 4:01 · 336 views
LeetCode 1019 Next Greater Node In Linked List - PythonRan Fang · 25:06 · 324 views
米开：LeetCode 1019. Next Greater Node In LinkedListM.C米开朗基罗 · 7:21 · 241 views
Leetcode-1019 : Next Greater Node in Linked List (Helper Model/Potential Candidates Method)Kumar Sanjeev · 5:59 · 215 views
The problem
You are given the head of a linked list with n nodes.
For each node in the list, find the value of the next greater node. That is, for each node, find the value of the first node that is next to it and has a strictly larger value than it.
Return an integer array answer where answer[i] is the value of the next greater node of the ith node (1-indexed). If the ith node does not have a next greater node, set answer[i] = 0.
Example 1:
Input: head = [2,1,5] Output: [5,5,0]
Example 2:
Input: head = [2,7,4,3,5] Output: [7,0,5,5,0]
Constraints:
- The number of nodes in the list is
n. 1 <= n <= 1041 <= Node.val <= 109
Approach overview
Problem Overview: You receive the head of a singly linked list. For every node, return the value of the next node to the right that has a strictly greater value. If no such node exists, return 0 for that position. The result is returned as an array aligned with the node order.
Approach 1: Monotonic Stack with Array Conversion (O(n) time, O(n) space)
Traverse the linked list once and copy all node values into an array. This converts the problem into the classic “next greater element” problem. Iterate through the array while maintaining a monotonic stack that stores indices of elements whose next greater value hasn't been found yet. When the current value is greater than the value at the stack's top index, pop that index and set its answer to the current value. Push the current index afterward. Each index is pushed and popped at most once, which guarantees O(n) time. This is the most common and interview-friendly solution.
Approach 2: Reverse Traversal with Stack (O(n) time, O(n) space)
Instead of processing from left to right, first convert the linked list into an array, then traverse it from right to left. Maintain a stack that keeps candidate values in decreasing order. For each element, pop all stack values less than or equal to the current value since they cannot be the next greater element. The remaining top of the stack is the next greater value. Record it and push the current value onto the stack. This approach still uses a stack but avoids storing indices. Time complexity remains O(n) and space complexity is O(n) for the stack and output.
Recommended for interviews: The monotonic stack approach is what interviewers typically expect. Converting the list to an array simplifies traversal and aligns with the standard “next greater element” pattern seen in many stack-based problems. Explaining the brute-force intuition (checking each node against all future nodes) shows understanding, but implementing the monotonic stack solution demonstrates mastery of linear-time optimization.
Approach 1: Monotonic Stack Approach
This approach leverages a monotonic stack to efficiently find the next greater element for each node in the linked list. By traversing the linked list once, we can maintain a stack to track potentially greater nodes and update results as we traverse.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def nextLargerNodes(self, head: ListNode) -> list[int]:
result = []
stack = []
current = head
index = 0
while current:
while stack and stack[-1][0] < current.val:
_, idx = stack.pop()
result[idx] = current.val
stack.append((current.val, index))
result.append(0)
current = current.next
index += 1
return resultimport java.util.*;
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public int[] nextLargerNodes(ListNode head) {
List<Integer> result = new ArrayList<>();
Stack<int[]> stack = new Stack<>();
ListNode current = head;
int index = 0;
while (current != null) {
while (!stack.isEmpty() && stack.peek()[0] < current.val) {
int[] pair = stack.pop();
result.set(pair[1], current.val);
}
stack.push(new int[]{current.val, index});
result.add(0);
current = current.next;
index++;
}
return result.stream().mapToInt(i->i).toArray();
}
}#include <vector>
#include <stack>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
std::vector<int> nextLargerNodes(ListNode* head) {
std::vector<int> result;
std::stack<std::pair<int, int>> s;
ListNode* current = head;
int index = 0;
while (current) {
while (!s.empty() && s.top().first < current->val) {
result[s.top().second] = current->val;
s.pop();
}
s.push({current->val, index});
result.push_back(0);
current = current->next;
index++;
}
return result;
}function ListNode(val) {
this.val = val;
this.next = null;
}
function nextLargerNodes(head) {
let result = [];
let stack = [];
let current = head;
let index = 0;
while (current !== null) {
while (stack.length > 0 && stack[stack.length - 1][0] < current.val) {
let [value, idx] = stack.pop();
result[idx] = current.val;
}
stack.push([current.val, index]);
result.push(0);
current = current.next;
index++;
}
return result;
}#include <stdio.h>
#include <stdlib.h>
// Definition for singly-linked list.
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode** createStack(int n) {
return (struct ListNode**)malloc(n * sizeof(struct ListNode*));
}
int* nextLargerNodes(struct ListNode* head, int* returnSize) {
int *results = (int*)malloc(10000 * sizeof(int));
struct ListNode **stack = createStack(10000);
int *stackIndex = (int*)malloc(10000 * sizeof(int));
int top = -1, index = 0;
struct ListNode *current = head;
while (current) {
while (top >= 0 && stack[top]->val < current->val) {
results[stackIndex[top--]] = current->val;
}
stack[++top] = current;
stackIndex[top] = index;
results[index++] = 0;
current = current->next;
}
*returnSize = index;
return results;
}using System;
using System.Collections.Generic;
public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
public int[] NextLargerNodes(ListNode head) {
List<int> result = new List<int>();
Stack<int[]> stack = new Stack<int[]>();
int index = 0;
ListNode current = head;
while (current != null) {
while (stack.Count > 0 && stack.Peek()[0] < current.val) {
var top = stack.Pop();
result[top[1]] = current.val;
}
stack.Push(new int[] {current.val, index});
result.Add(0);
current = current.next;
index++;
}
return result.ToArray();
}
}This Python solution makes use of a list as a makeshift stack to track indices and values. It efficiently computes the next greater nodes in linear time as it traverses the list.
Time Complexity: O(n)
Space Complexity: O(n)
Approach 2: Reverse Traversal with Stack Approach
In this approach, reverse the linked list initially and then traverse, keeping track of the next greatest node using a stack. As this traversal is reversed, use a stack to efficiently find and keep the nearest greatest value.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
prev = None
while head:
next_node = head.next
head.next = prev
prev = head
head = next_node
return prev
def nextLargerNodes(self, head: ListNode) -> list[int]:
head = self.reverseList(head)
stack = []
result = []
while head:
while stack and stack[-1] <= head.val:
stack.pop()
result.append(0 if not stack else stack[-1])
stack.append(head.val)
head = head.next
result.reverse()
return resultclass ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
private ListNode reverseList(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
public int[] nextLargerNodes(ListNode head) {
head = reverseList(head);
Stack<Integer> stack = new Stack<>();
List<Integer> result = new ArrayList<>();
while (head != null) {
while (!stack.isEmpty() && stack.peek() <= head.val)
stack.pop();
result.add(stack.isEmpty() ? 0 : stack.peek());
stack.push(head.val);
head = head.next;
}
Collections.reverse(result);
return result.stream().mapToInt(i -> i).toArray();
}
}#include <vector>
#include <stack>
#include <algorithm>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
while (head != nullptr) {
ListNode* next = head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}
std::vector<int> nextLargerNodes(ListNode* head) {
head = reverseList(head);
std::vector<int> result;
std::stack<int> stack;
while (head) {
while (!stack.empty() && stack.top() <= head->val)
stack.pop();
result.push_back(stack.empty() ? 0 : stack.top());
stack.push(head->val);
head = head->next;
}
std::reverse(result.begin(), result.end());
return result;
}function ListNode(val) {
this.val = val;
this.next = null;
}
function reverseList(head) {
let prev = null;
while (head) {
let next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
function nextLargerNodes(head) {
head = reverseList(head);
let result = [];
let stack = [];
while (head !== null) {
while (stack.length > 0 && stack[stack.length - 1] <= head.val) {
stack.pop();
}
result.push(stack.length === 0 ? 0 : stack[stack.length - 1]);
stack.push(head.val);
head = head.next;
}
return result.reverse();
}#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* prev = NULL;
struct ListNode* current = head;
while (current) {
struct ListNode* next_node = current->next;
current->next = prev;
prev = current;
current = next_node;
}
return prev;
}
int* nextLargerNodes(struct ListNode* head, int* returnSize) {
head = reverseList(head);
int *result = (int*)malloc(10000 * sizeof(int));
int *stack = (int*)malloc(10000 * sizeof(int));
int top = -1, idx = 0;
struct ListNode *current = head;
while (current) {
while (top >= 0 && stack[top] <= current->val) {
top--;
}
result[idx++] = (top == -1) ? 0 : stack[top];
stack[++top] = current->val;
current = current->next;
}
for (int i = 0, j = idx - 1; i < j; i++, j--) { // Reverse the result back
int temp = result[i];
result[i] = result[j];
result[j] = temp;
}
*returnSize = idx;
return result;
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
private ListNode ReverseList(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
public int[] NextLargerNodes(ListNode head) {
head = ReverseList(head);
Stack<int> stack = new Stack<int>();
List<int> result = new List<int>();
while (head != null) {
while (stack.Count > 0 && stack.Peek() <= head.val)
stack.Pop();
result.Add(stack.Count == 0 ? 0 : stack.Peek());
stack.Push(head.val);
head = head.next;
}
result.Reverse();
return result.ToArray();
}
}The Python solution reverses the initial linked list and applies a similar stack methodology to determine the next greater nodes. Finally, it reverses the result before returning.
Time Complexity: O(n)
Space Complexity: O(n)
Approach 3: Monotonic Stack
The problem requires finding the next larger node for each node in the linked list, that is, finding the first node to the right of each node in the linked list that is larger than it. We first traverse the linked list and store the values in the linked list in an array nums. For each element in the array nums, we just need to find the first element to its right that is larger than it. The problem of finding the next larger element can be solved using a monotonic stack.
We traverse the array nums from back to front, maintaining a stack stk that is monotonically decreasing from the bottom to the top. During the traversal, if the top element of the stack is less than or equal to the current element, we loop to pop the top element of the stack until the top element of the stack is larger than the current element or the stack is empty.
If the stack is empty at this time, it means that the current element does not have a next larger element, otherwise, the next larger element of the current element is the top element of the stack, and we update the answer array ans. Then we push the current element into the stack and continue the traversal.
After the traversal is over, we return the answer array ans.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the linked list.
/**
* Definition for singly-linked list.
* 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)
* }
* }
*/
function nextLargerNodes(head: ListNode | null): number[] {
const nums: number[] = [];
while (head) {
nums.push(head.val);
head = head.next;
}
const stk: number[] = [];
const n = nums.length;
const ans: number[] = Array(n).fill(0);
for (let i = n - 1; ~i; --i) {
while (stk.length && stk.at(-1)! <= nums[i]) {
stk.pop();
}
ans[i] = stk.length ? stk.at(-1)! : 0;
stk.push(nums[i]);
}
return ans;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func nextLargerNodes(head *ListNode) []int {
nums := []int{}
for ; head != nil; head = head.Next {
nums = append(nums, head.Val)
}
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
}// 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
// }
// }
// }
use std::collections::VecDeque;
impl Solution {
pub fn next_larger_nodes(head: Option<Box<ListNode>>) -> Vec<i32> {
let mut nums = Vec::new();
let mut current = &head;
while let Some(node) = current {
nums.push(node.val);
current = &node.next;
}
let mut stk = VecDeque::new();
let n = nums.len();
let mut ans = vec![0; n];
for i in (0..n).rev() {
while !stk.is_empty() && stk.back().copied().unwrap() <= nums[i] {
stk.pop_back();
}
if let Some(&top) = stk.back() {
ans[i] = top;
}
stk.push_back(nums[i]);
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Monotonic Stack Approach | Time Complexity: O(n) |
| Reverse Traversal with Stack Approach | Time Complexity: O(n) |
| Monotonic Stack | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Scan | O(n²) | O(1) | Good for explaining the basic idea or very small lists |
| Monotonic Stack with Array | O(n) | O(n) | Best general solution; standard next greater element pattern |
| Reverse Traversal with Stack | O(n) | O(n) | Useful when scanning from right and keeping decreasing stack of values |
Frequently asked questions
Is Next Greater Node In Linked List easy or hard?
Next Greater Node In Linked List is rated Medium on LeetCode. The difficulty comes from recognizing the next greater element pattern and applying a monotonic stack to reduce the naive O(n²) approach to an O(n) solution.
Next Greater Node In Linked List Python/Java solution
Python and Java implementations typically convert the linked list to an array and then apply the monotonic stack technique. A stack tracks indices whose next greater value has not yet been found. When a larger value appears, the algorithm updates results for all smaller elements on the stack.
How to solve Next Greater Node In Linked List in O(n)?
First convert the linked list into an array of values. Traverse the array while maintaining a monotonic decreasing stack of indices. When the current value is greater than the value at the index on the stack top, pop that index and set its answer to the current value. Continue until the stack condition holds, then push the current index.
What is the best approach for Next Greater Node In Linked List?
The most efficient approach uses a monotonic stack after converting the linked list to an array. Iterate through the values while maintaining a decreasing stack of indices. When a larger value appears, pop indices from the stack and update their result. This processes each element once, giving O(n) time complexity.
Is Next Greater Node In Linked List asked at Google/Amazon/Meta?
Next greater element style problems are frequently asked in interviews at companies like Amazon, Google, and Meta. Variants involving arrays, stacks, and monotonic stacks appear regularly because they test pattern recognition and linear-time optimization techniques.
What data structure is used in Next Greater Node In Linked List?
The key data structure is a monotonic stack. It stores indices or values in decreasing order so that the next greater element can be determined efficiently. Arrays are also used after converting the linked list to allow indexed access.
What is the time complexity of Next Greater Node In Linked List?
The optimal solution runs in O(n) time where n is the number of nodes. Each node index is pushed to and popped from the stack at most once. The space complexity is O(n) for storing the array of values and the result array.