Next Greater Node In Linked List: Monotonic Stack on Lists

LeetCode 1019, Next Greater Node In Linked List, gives you the head of a linked list and asks you to return an integer array answer where answer[i] is the value of the next node with a strictly greater value than node i. If no such node exists, answer[i] = 0. It is a medium-difficulty problem that bridges two fundamental patterns: linked list traversal and the monotonic stack.

Why this problem matters

If you have solved "Next Greater Element" on an array, you already know the core algorithm. The twist here is that the input arrives as a linked list rather than an array. That means you cannot index into it directly, and you have to decide how to handle the conversion before applying the stack logic. This problem is a great test of whether you can recognize a known pattern hiding behind a different data structure.

The monotonic stack is one of the most versatile tools in the stack category. It shows up in Daily Temperatures, Next Greater Element I and II, Online Stock Span, and Largest Rectangle in Histogram. All of these problems share the same core loop: for each element, pop everything on the stack that is "smaller" (or "less than"), because the current element resolves those waiting entries. Once you can write that loop from memory, this entire family of problems becomes approachable.

Combining linked list traversal with a stack also tests your ability to decompose a problem into independent sub-problems. First, convert the list to an array. Then apply the stack. Neither step is hard on its own, but you need to see the decomposition clearly.

The key insight

The approach has two phases. First, walk the linked list from head to tail and collect all values into an array. This gives you random access by index, which the stack algorithm needs. Second, iterate through the array and use a monotonic decreasing stack. For each element, pop everything on the stack that has a smaller value, because the current element IS their next greater node. Then push the current index onto the stack.

When you pop an index from the stack, you know the current element is the first one to the right that is strictly greater. So you set result[popped_index] = current_value. Any indices left on the stack at the end have no greater node after them, and their result stays 0.

This is the exact same logic as Next Greater Element I and II, just with a linked list as the input format. The linked list does not change the algorithm at all. It only changes how you access the data.

The solution

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def next_larger_nodes(head: ListNode) -> list[int]:
    values = []
    node = head
    while node:
        values.append(node.val)
        node = node.next

    result = [0] * len(values)
    stack = []

    for i, val in enumerate(values):
        while stack and values[stack[-1]] < val:
            idx = stack.pop()
            result[idx] = val
        stack.append(i)

    return result

The first loop converts the linked list into an array called values. You walk from head to the end, appending each node's value. This is O(n) time and O(n) space.

The second section initializes result as all zeros and creates an empty stack. The stack will hold indices into the values array.

The for loop walks left to right through values. The while loop checks whether the current value is strictly greater than the value at the top of the stack. If it is, that means the current element is the "next greater node" for the index on top. You pop it and record result[idx] = val. You keep popping as long as the condition holds, because the current value might resolve multiple waiting entries at once.

After the while loop, you push the current index. It is now waiting for its own next greater node.

When the for loop finishes, any indices still on the stack never found a greater node. Their entries in result remain 0, which is exactly what the problem asks for.

Visual walkthrough

Notice how step 3 is where most of the action happens. Value 5 is greater than both entries on the stack (1 and 2), so it pops both of them in a single pass through the while loop. Each index is pushed exactly once and popped at most once across the entire algorithm. That is why the total work is O(n) even though individual iterations can pop multiple elements.

Also notice that step 4 is just cleanup. Any index left on the stack at the end has no greater node to its right. The result array was initialized to 0, so there is nothing more to do.

Complexity analysis

Time: O(n). The linked list traversal is O(n). The stack pass is also O(n) because each of the n indices is pushed once and popped at most once. The while loop may pop multiple entries in a single iteration, but the total number of pops across all iterations is at most n.

Space: O(n). The values array, result array, and stack all use O(n) space. In the worst case (strictly decreasing list), the stack holds all n indices before anything gets popped.

The building blocks

1. Linked list to array conversion

The first step strips away the linked list structure and gives you an array to work with:

values = []
node = head
while node:
    values.append(node.val)
    node = node.next

This is a standard traversal. You could also process nodes directly without converting to an array by tracking an index counter, but having the full array makes the stack logic cleaner because you can look up values[stack[-1]] at any time.

2. Monotonic decreasing stack

The core loop that resolves "next greater" queries:

stack = []
for i, val in enumerate(values):
    while stack and values[stack[-1]] < val:
        idx = stack.pop()
        result[idx] = val
    stack.append(i)

The stack maintains a decreasing order of values from bottom to top. Every time you encounter a value that breaks this pattern (it is greater than the top), you pop and resolve. This is the same building block used in Daily Temperatures (where you record distance instead of value), Next Greater Element I (where you store results in a hash map), and Online Stock Span (where you accumulate spans).

Edge cases

Before submitting, make sure your solution handles:

• Single node like [5]: result is [0]. The stack never pops anything.
• Strictly increasing like [1, 2, 3, 4]: each node's next greater is the immediate next node. Result is [2, 3, 4, 0]. Each push immediately pops the previous entry.
• Strictly decreasing like [4, 3, 2, 1]: no node has a greater node to its right. Result is [0, 0, 0, 0]. The stack grows to n elements and nothing gets popped.
• All equal values like [5, 5, 5]: equal is not strictly greater, so every answer is 0.
• Large spike at the end like [1, 2, 1, 2, 1, 100]: the last node clears the entire stack, resolving every waiting index.
• Duplicates with a greater value later like [2, 2, 3]: both 2s get resolved when you reach 3. Result is [3, 3, 0].

From understanding to recall

You have walked through the full solution step by step. The two-phase approach (convert to array, then monotonic stack) is clean and composable. But recognizing that this is a "next greater element" problem when the input is a linked list requires pattern recognition, and writing the stack loop correctly under pressure requires muscle memory.

The subtle details matter. The comparison is strictly <, not <=. You store indices on the stack, not values. You set result[idx] = val (the current value), not the distance. These are the kinds of things that slip under time pressure, not because the algorithm is complex, but because the implementation has small details you need to get exactly right.

Spaced repetition locks in both the pattern recognition and the implementation details. You practice converting a linked list to an array, writing the monotonic stack loop, and assembling the two pieces. After a few repetitions at increasing intervals, you can write this solution from scratch in under five minutes.

Related posts

• Daily Temperatures - The classic monotonic stack problem that teaches the "next greater" pattern on arrays
• Next Greater Element I - The hash map plus monotonic stack variation for mapping between two arrays
• Online Stock Span - Another monotonic stack problem where you track spans of decreasing elements

CodeBricks breaks the "next greater element" pattern into its core building blocks and drills each one separately. You practice the monotonic stack loop, the linked list traversal, and the full combined solution at spaced intervals. When this problem or any of its variants appears in an interview, you recognize it immediately and write the code without hesitation.