LeetCode 1019: Next Greater Node In Linked List

Problem Restatement

We are given the head of a singly linked list.

For each node, we want to find the value of the next node that has a strictly greater value.

If no such node exists, the answer for that node is 0.

Return an array of these answers.

The official constraints state that the number of nodes is in [1, 10^4] and 1 <= Node.val <= 10^9.

Input and Output

Function shape:

def nextLargerNodes(head: Optional[ListNode]) -> list[int]:
    ...

Examples

Example 1:

head = [2, 1, 5]

Answer:

[5, 5, 0]

Example 2:

head = [2, 7, 4, 3, 5]

Answer:

[7, 0, 5, 5, 0]

Key Insight

This is the classic “next greater element” problem.

Use a monotonic stack:

• Maintain a stack of indices whose next greater element has not yet been found.
• For each new value, pop all indices from the stack whose values are smaller than the current value.
• The current value is the next greater element for all those popped indices.

Algorithm

1. Convert the linked list to an array of values.
2. Initialize result = [0] * n.
3. Use a stack of indices.
4. For each index i and value v:
   • While the stack is non-empty and values[stack[-1]] < v:
     • Pop j from the stack.
     • result[j] = v.
   • Push i onto the stack.
5. Return result.

Correctness

The stack always contains indices in increasing order with values in decreasing order (monotone decreasing from bottom to top).

When a new value v is larger than the value at the top of the stack, the top’s next greater element is v.

After processing all elements, remaining stack entries have no next greater element, so they keep their default value of 0.

Edge Cases

• The stack should store exactly the unresolved items needed by the invariant.
• Process equal values deliberately; many monotonic-stack problems differ only in < versus <=.
• Flush or inspect the remaining stack after the scan if unresolved items still contribute to the answer.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

from typing import Optional

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]:
        values = []
        node = head
        while node:
            values.append(node.val)
            node = node.next

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

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

        return result

Code Explanation

Convert linked list to array:

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

Use a monotonic stack of indices:

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

When v is larger than the value at index stack[-1], that index’s next greater element is v.

Remaining stack entries keep result[j] = 0.

Testing

def make_list(vals):
    dummy = ListNode()
    cur = dummy
    for v in vals:
        cur.next = ListNode(v)
        cur = cur.next
    return dummy.next

def run_tests():
    s = Solution()

    assert s.nextLargerNodes(make_list([2, 1, 5])) == [5, 5, 0]
    assert s.nextLargerNodes(make_list([2, 7, 4, 3, 5])) == [7, 0, 5, 5, 0]
    assert s.nextLargerNodes(make_list([1, 7, 5, 1, 9, 2, 5, 1])) == [7, 9, 9, 9, 0, 5, 0, 0]
    assert s.nextLargerNodes(make_list([1])) == [0]

    print("all tests passed")

run_tests()