Next Greater Node in Linked List Solution

Problem

Given a singly linked list, find the next larger value for each node — the value of the first subsequent node with a strictly greater value. Return an array indexed by position, using 0 wherever no larger node exists.

→

→∅

[2,7,4,3,5]

Input: head = [2, 7, 4, 3, 5]
Output: [7, 0, 5, 5, 0]
Explanation: Node 2's first larger successor is 7; node 7 has no larger successor; nodes 4 and 3 both have 5 as their first larger successor; node 5 is the last.

Intuition

This is the classic "next greater element" problem applied to a linked list. The key observation is that you can't look ahead in a linked list, so you need a way to remember indices you haven't resolved yet and fill them in later. A monotonic stack does exactly that: it holds indices whose answers are still pending, and whenever a new value is larger than the current stack top, you pop and record the answer for those positions.

Approach 1 — Brute Force

Convert the linked list to an array, then for each position scan rightward until finding a strictly larger value or exhausting the array.

Traverse the linked list once, collecting values into an array
Initialize the answer array to all zeros
For each index i, iterate j = i+1, i+2, ... until you find values[j] > values[i]
When found, set answer[i] = values[j] and break
Return the answer array

1def nextLargerNodes(self, head):
2    values = []
3    node = head
4    while node:
5        values.append(node.val)
6        node = node.next
7
8    answer = [0] * len(values)
9    for i in range(len(values)):
10        for j in range(i + 1, len(values)):
11            if values[j] > values[i]:
12                answer[i] = values[j]
13                break
14    return answer

Time: O(n²) — each element may scan the entire remaining list.
Space: O(n) — the values array and answer array each hold n elements.

Approach 2 — Monotonic Stack (One Pass)

Use a stack to track indices whose next greater value hasn't been found yet. The stack stays monotonically decreasing in value — whenever a new element is larger than the stack top, it becomes the answer for everything below it on the stack.

Traverse the list once, collecting values
Initialize the answer array to zeros
Maintain a stack of indices (pending — no next-greater found yet)
For each index i, while the stack is non-empty and values[stack.top()] < values[i], pop the top and set answer[top] = values[i]
Push i onto the stack
Any indices left in the stack at the end have no next-greater node (answer stays 0)

1def nextLargerNodes(self, head):
2    values = []
3    node = head
4    while node:
5        values.append(node.val)
6        node = node.next
7
8    answer = [0] * len(values)
9    pending_indices = []  # monotonically decreasing stack of indices
10
11    for i, val in enumerate(values):
12        # resolve all pending indices smaller than the current value
13        while pending_indices and values[pending_indices[-1]] < val:
14            resolved_idx = pending_indices.pop()
15            answer[resolved_idx] = val
16        pending_indices.append(i)
17
18    return answer

Time: O(n) — each index is pushed and popped at most once.
Space: O(n) — the stack holds at most n indices; the answer array holds n elements.

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n²)	O(n)	Explaining initial reasoning — never in production
Monotonic Stack	O(n)	O(n)	Always — standard pattern for any "next greater" problem

Common Mistakes

Popping only once instead of in a loop: When a new value resolves several pending indices at once (e.g. a large value at the end), you must keep popping until the stack top is no longer smaller — a single pop misses those earlier elements.
Pushing values instead of indices: The stack must store indices so you can write into the correct position in the answer array; storing the values themselves loses that positional information.
Using <= instead of < in the comparison: The problem asks for strictly greater, so equal values must not resolve each other — using <= produces wrong answers for inputs with duplicates like [3, 3, 1, 3].
Forgetting to convert the linked list first: Trying to run the stack directly on list nodes while traversing adds complexity without benefit; converting to an array upfront makes the algorithm cleaner and avoids re-traversal.
Assuming leftover stack indices need special handling: The answer array is initialized to zeros, so any index still in the stack after the loop already has the correct answer (0) — no extra cleanup needed.

Next Greater Node in Linked List — Solution