# Next Greater Node In Linked List
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/next-greater-node-in-linked-list)
Canonical: https://scaleengineer.com/dsa/problems/next-greater-node-in-linked-list
**Data structures:** Array, Linked List, Stack, Monotonic Stack
---
## 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:**

![](https://assets.glich.co/dsa/next-greater-node-in-linked-list/image0.jpg) 

**Input:** head = [2,1,5]
**Output:** [5,5,0]

**Example 2:**

![](https://assets.glich.co/dsa/next-greater-node-in-linked-list/image1.jpg) 

**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 <= 104`
* `1 <= Node.val <= 109`

# Approaches
## Brute Force with Nested Loops
This approach iterates through each node of the linked list. For each node, it performs a second iteration through all the subsequent nodes to find the first one with a strictly greater value. It's straightforward but computationally expensive.
**Time:** O(n^2), where n is the number of nodes. The nested loops are the bottleneck. For each element, we might scan through all the remaining elements in the worst-case scenario (e.g., a list sorted in descending order). · **Space:** O(n), where n is the number of nodes in the linked list. This space is used to store the node values in an `ArrayList` and for the final `answer` array.
**Pros:** Simple to understand and implement.; Requires minimal complex data structures.
**Cons:** Highly inefficient for large inputs due to its O(n^2) time complexity.; Likely to result in a "Time Limit Exceeded" error on platforms like LeetCode for the given constraints.
### Explanation
The brute-force method is the most intuitive way to solve the problem. The core idea is to check every possible pair of nodes `(i, j)` where node `j` appears after node `i`.

To make the implementation simpler, we first traverse the linked list and store all its node values in a dynamic array, like an `ArrayList` in Java. This conversion allows us to use indices, which is more convenient than using pointers for this specific logic.

Once we have the values in an array, we create a result array `answer` of the same size, initialized to all zeros. Then, we use a pair of nested loops. The outer loop picks an element, and the inner loop scans the rest of the array to its right to find the first element that is larger than the one picked by the outer loop. When a larger element is found, we record its value in our `answer` array and break the inner loop to proceed to the next element in the outer loop. If the inner loop finishes without finding a greater element, the default value of 0 remains, which correctly signifies that no next greater node exists.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] nextLargerNodes(ListNode head) {
        // Convert linked list to an ArrayList for easier access.
        List<Integer> list = new ArrayList<>();
        for (ListNode node = head; node != null; node = node.next) {
            list.add(node.val);
        }
        
        int n = list.size();
        int[] answer = new int[n];
        
        // Use nested loops to find the next greater node.
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (list.get(j) > list.get(i)) {
                    answer[i] = list.get(j);
                    break; // Found the first greater node, so we can stop searching.
                }
            }
            // If no greater node is found, answer[i] remains 0 by default.
        }
        
        return answer;
    }
}
```
### Algorithm
1. Convert the input linked list into an `ArrayList` of integers to facilitate easy access to elements by index.
2. Get the size `n` of the list.
3. Initialize an integer array `answer` of size `n` with all elements set to 0.
4. Iterate through the `ArrayList` with an index `i` from `0` to `n-1`.
5. For each `i`, start a nested inner loop with index `j` from `i+1` to `n-1`.
6. Inside the inner loop, if the element at index `j` is strictly greater than the element at index `i`, it means we have found the next greater node.
7. Set `answer[i]` to the value of this greater element (`list.get(j)`) and immediately `break` the inner loop, as we only need the first greater node.
8. If the inner loop completes without finding any greater element, `answer[i]` remains `0`.
9. After the outer loop finishes, return the `answer` array.

## Monotonic Stack with List Reversal
A much more efficient approach utilizes a monotonic stack. By reversing the linked list first, we can process nodes from tail to head (of the original list). This allows us to use a stack to keep track of potential greater nodes seen so far, enabling us to find the next greater element for each node in a single pass.
**Time:** O(n), where n is the number of nodes. The list reversal takes O(n). The subsequent traversal of the reversed list also takes O(n), as each element is pushed onto and popped from the stack at most once. Therefore, the total time complexity is linear. · **Space:** O(n), where n is the number of nodes. The space is required for the `answer` array and the stack. In the worst-case scenario (a list sorted in ascending order), the stack might hold all `n` elements.
**Pros:** Optimal time complexity of O(n).; Efficiently solves the problem with a single pass after reversal.; A standard and powerful technique for "Next Greater Element" type problems.
**Cons:** The logic is more complex than the brute-force approach, involving list reversal and a monotonic stack.; Modifies the input linked list by reversing it. If the original list structure must be preserved, a copy should be made first, which would increase space complexity.
### Explanation
This optimal solution cleverly reframes the problem. Instead of searching forward for a "next greater node," we can reverse the list and search for a "previous greater node" relative to the reversed sequence. This is a classic problem pattern solvable efficiently with a monotonic stack.

The algorithm works as follows:
First, we reverse the linked list. This can be done iteratively with O(1) extra space. While reversing, we also count the number of nodes, `n`, which allows us to create the final `answer` array of the correct size upfront.

Next, we iterate through this reversed list. We use a stack that we'll maintain in a monotonically decreasing order. For each node we visit, we pop elements from the stack as long as they are less than or equal to the current node's value. The reason for this is that if the current node's value is greater, any of these smaller popped elements can never be the "next greater node" for any of the nodes that came before the current one (in the original list's order).

After popping, the element at the top of the stack (if any) is the first element we've encountered (from right to left in the original list) that is greater than the current node. This is exactly the next greater node. If the stack is empty, no such node exists. We store this result in our `answer` array. Since we are iterating through the reversed list, we fill the `answer` array from back to front to maintain the correct order.

Finally, we push the current node's value onto the stack to be a potential "next greater node" for the elements we will visit next.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
import java.util.Stack;

class Solution {
    public int[] nextLargerNodes(ListNode head) {
        // Step 1: Reverse the linked list and count its size.
        ListNode prev = null;
        ListNode curr = head;
        int n = 0;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
            n++;
        }
        ListNode revHead = prev;
        
        // Step 2: Initialize result array and stack.
        int[] answer = new int[n];
        Stack<Integer> stack = new Stack<>();
        int index = n - 1;
        
        // Step 3 & 4: Traverse the reversed list and use the monotonic stack.
        curr = revHead;
        while (curr != null) {
            // Pop elements from stack smaller than or equal to current value.
            while (!stack.isEmpty() && stack.peek() <= curr.val) {
                stack.pop();
            }
            
            // The top of the stack is the next greater element.
            if (stack.isEmpty()) {
                answer[index] = 0;
            } else {
                answer[index] = stack.peek();
            }
            
            // Push current value onto stack for future comparisons.
            stack.push(curr.val);
            
            curr = curr.next;
            index--;
        }
        
        return answer;
    }
}
```
### Algorithm
1. **Reverse the Linked List & Count Nodes:** Traverse the linked list to reverse it in-place. During this traversal, count the number of nodes, `n`.
2. **Initialize:** Create an integer array `answer` of size `n` and an empty `Stack<Integer>`.
3. **Traverse Reversed List:** Iterate through the reversed list, starting from its new head. Maintain an index pointer, `i`, starting from `n-1` and decrementing in each step.
4. **Use Monotonic Stack:** For each node `curr` in the reversed list:
   a. While the stack is not empty and the value at the top of the stack is less than or equal to the current node's value (`stack.peek() <= curr.val`), pop from the stack. This removes all elements that cannot be the next greater element for `curr` or any subsequent nodes in the original list.
   b. After the while loop, if the stack is empty, it means no greater element exists to its right (in the original list). Set `answer[i] = 0`.
   c. Otherwise, the value at the top of the stack (`stack.peek()`) is the first greater element. Set `answer[i] = stack.peek()`.
   d. Push the current node's value (`curr.val`) onto the stack.
   e. Decrement the index `i`.
5. **Return Result:** After iterating through the entire reversed list, the `answer` array is correctly populated. Return it.

# Solutions
### Java

```java
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public int [] nextLargerNodes ( ListNode head ) { List < Integer > nums = new ArrayList <>(); for (; head != null ; head = head . next ) { nums . add ( head . val ); } Deque < Integer > stk = new ArrayDeque <>(); int n = nums . size (); int [] ans = new int [ n ]; for ( int i = n - 1 ; i >= 0 ; -- i ) { while (! stk . isEmpty () && stk . peek () <= nums . get ( i )) { stk . pop (); } if (! stk . isEmpty ()) { ans [ i ] = stk . peek (); } stk . push ( nums . get ( i )); } return ans ; } }
```

### JavaScript

```javascript
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {number[]} */ var nextLargerNodes = function ( head ) { const nums = []; while ( head ) { nums . push ( head . val ); head = head . next ; } const stk = []; const n = nums . length ; const ans = new Array ( n ). fill ( 0 ); for ( let i = n - 1 ; i >= 0 ; -- i ) { while ( stk . length && stk [ stk . length - 1 ] <= nums [ i ]) { stk . pop (); } ans [ i ] = stk . length ? stk [ stk . length - 1 ] : 0 ; stk . push ( nums [ i ]); } return ans ; };
```

### CPP

```cpp
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: vector < int > nextLargerNodes ( ListNode * head ) { vector < int > nums ; for (; head ; head = head -> next ) { nums . push_back ( head -> val ); } stack < int > stk ; int n = nums . size (); vector < int > ans ( n ); for ( int i = n - 1 ; ~ i ; -- i ) { while ( ! stk . empty () && stk . top () <= nums [ i ]) { stk . pop (); } if ( ! stk . empty ()) { ans [ i ] = stk . top (); } stk . push ( nums [ i ]); } return ans ; } };
```

### Python

```python
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def nextLargerNodes ( self , head : Optional [ ListNode ]) -> List [ int ]: nums = [] while head : nums . append ( head . val ) head = head . next stk = [] n = len ( nums ) ans = [ 0 ] * n for i in range ( n - 1 , - 1 , - 1 ): while stk and stk [ - 1 ] <= nums [ i ]: stk . pop () if stk : ans [ i ] = stk [ - 1 ] stk . append ( nums [ i ]) return ans
```