Next Greater Node in Linked List — Monotonic Stack Explained Step by Step

Problem Statement#

LeetCode 1019 — Next Greater Node In Linked List Difficulty: Medium | Pattern: Monotonic Stack

You are given the head of a linked list with n nodes. For each node, find the value of the next node that has a strictly greater value. Return an integer array answer where answer[i] is the value of the next greater node of the ith node (1-indexed). If there is no such node, set answer[i] = 0.

Constraints:

• Number of nodes: 1 <= n <= 10^4
• Node values: 1 <= Node.val <= 10^9

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]

Why This Problem Matters#

The "next greater element" is one of the most fundamental patterns in competitive programming and technical interviews. It shows up at Amazon, Adobe, and Walmart Labs — companies that love testing whether candidates know when to reach for a monotonic stack instead of brute-forcing nested loops.

What makes this variant trickier than the classic "Next Greater Element I" (LC 496) is that the input is a linked list, not an array. You cannot jump to an arbitrary index; you must traverse sequentially. This forces candidates to think about how to convert the problem into something stack-friendly before applying the stack logic.

Interviewers love this problem because it simultaneously tests three skills: linked list traversal, array indexing, and stack mechanics. It is a medium-difficulty question that many candidates struggle with in the allotted 20–25 minutes because they approach it naively with an O(n²) double loop.

Understanding the monotonic stack pattern here also unlocks a family of related problems: next greater element, daily temperatures (LC 739), largest rectangle in histogram, and trapping rain water. This single pattern accounts for a significant fraction of stack-based interview questions asked across the industry.

The Core Insight#

The key realization is this: a monotonic decreasing stack lets you process each element once and resolve its "next greater" answer the moment you find it.

As you walk through the values, maintain a stack of indices whose answers you have not yet determined. Whenever you see a new value that is larger than the value at the top of the stack, you have found the next greater element for the index at the top. Pop it, record the answer, and continue.

Because each element is pushed and popped at most once, the total work is O(n) — a massive improvement over the O(n²) brute force.

The secondary insight is to convert the linked list to an array first. Since linked lists do not allow random access, you do a single O(n) traversal to build a values array, then apply the monotonic stack on that array. This two-step approach keeps the code clean, readable, and easy to verify in an interview setting.

Visual Dry Run#

Input: [2, 7, 4, 3, 5]

Final answer: [7, 0, 5, 5, 0]

Solution (Optimal)#

from typing import Optional, List
 
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def nextLargerNodes(head: Optional[ListNode]) -> List[int]:
    # Step 1: Convert linked list to array
    values = []
    curr = head
    while curr:
        values.append(curr.val)
        curr = curr.next
 
    n = len(values)
    answer = [0] * n
    stack = []  # stores indices where we have not found next greater yet
 
    # Step 2: Monotonic decreasing stack
    for i, val in enumerate(values):
        # While current value resolves pending indices
        while stack and values[stack[-1]] < val:
            idx = stack.pop()
            answer[idx] = val
        stack.append(i)
 
    # Remaining indices have no next greater — answer stays 0
    return answer

function nextLargerNodes(head) {
    // Step 1: Collect values from linked list
    const values = [];
    let curr = head;
    while (curr) {
        values.push(curr.val);
        curr = curr.next;
    }
 
    const n = values.length;
    const answer = new Array(n).fill(0);
    const stack = []; // stores indices
 
    // Step 2: Monotonic stack
    for (let i = 0; i < n; i++) {
        while (stack.length > 0 && values[stack[stack.length - 1]] < values[i]) {
            const idx = stack.pop();
            answer[idx] = values[i];
        }
        stack.push(i);
    }
 
    return answer;
}

Complexity:

Common Mistakes#

1. Brute force double loop: Checking every pair is O(n²). Always think "monotonic stack" when you see "next greater."
2. Forgetting to convert to array: Trying to run the stack directly on the linked list makes index management error-prone and code hard to reason about.
3. Wrong stack invariant: The stack should hold indices of nodes whose next greater has NOT been found yet — this means the values at those indices are in decreasing order (a decreasing stack).
4. Off-by-one confusion: The problem says 1-indexed in the description but the output array is 0-indexed. Your loop naturally uses 0-indexed so no adjustment is needed.
5. Not initializing answer to 0: If you forget to zero-initialize, leftover garbage values corrupt the output for indices that never get a match.

Interview Tips#

• Say it out loud: "The naive O(n²) approach would check every pair. I can do better with a monotonic stack in O(n)."
• Draw the stack operations: Physically tracing push and pop on a whiteboard impresses interviewers and helps you catch bugs.
• Explain the invariant: "I maintain a decreasing stack of indices. When I encounter a larger value, it resolves all pending smaller indices."
• Handle edge cases: Clarify whether head can be null. Per constraints n is at least 1, but it is good practice to mention it.
• Mention tradeoffs: The values array uses O(n) extra space. If space is critical you could traverse the list twice with different logic, but the array approach is cleaner.

Follow-up Questions#

1. What if the list is circular? You would need to handle the wrap-around, typically by processing 2n elements.
2. Can you solve it in a single pass without converting to an array? Yes, but requires more careful index bookkeeping — the array approach is preferred in interviews.
3. What about "next smaller element"? Flip the stack invariant to a monotonic increasing stack.
4. LeetCode 739 — Daily Temperatures: Same pattern — values represent temperatures. Apply the same template.
5. LeetCode 496 — Next Greater Element I: Simpler version with two arrays instead of a linked list.
6. What if we want the distance to the next greater, not its value? Subtract indices instead of recording values.

Key Takeaways#

• Convert the linked list to an array first; this makes index management trivial and keeps the stack logic clean.
• A monotonic decreasing stack of indices is the canonical O(n) solution for all "next greater element" variants.
• Each element is pushed and popped at most once, giving O(n) total time complexity with O(n) space.
• Indices left in the stack after traversal have no next greater node — their answer remains 0.
• This pattern generalizes to daily temperatures, largest rectangle in histogram, and trapping rain water.
• Mastering this problem unlocks a whole family of stack-based interview questions asked at Amazon, Adobe, and beyond.