# 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

| Item | Meaning |
|---|---|
| Input | Head of a singly linked list |
| Output | Array where `result[i]` is the next greater value for node `i`, or `0` |

Function shape:

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

## Examples

Example 1:

```python
head = [2, 1, 5]
```

| Node | Value | Next Greater |
|---|---:|---:|
| 0 | 2 | 5 |
| 1 | 1 | 5 |
| 2 | 5 | 0 |

Answer:

```python
[5, 5, 0]
```

Example 2:

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

| Node | Value | Next Greater |
|---|---:|---:|
| 0 | 2 | 7 |
| 1 | 7 | 0 |
| 2 | 4 | 5 |
| 3 | 3 | 5 |
| 4 | 5 | 0 |

Answer:

```python
[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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each element is pushed and popped at most once |
| Space | `O(n)` | Stack and result array |

## 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

```python
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:

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

Use a monotonic stack of indices:

```python
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

```python
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()
```

| Test | Expected | Why |
|---|---|---|
| `[2,1,5]` | `[5,5,0]` | Both 2 and 1 see 5 as next greater |
| `[2,7,4,3,5]` | `[7,0,5,5,0]` | Standard monotonic stack result |
| `[1,7,5,1,9,2,5,1]` | `[7,9,9,9,0,5,0,0]` | 9 resolves many pending nodes |
| `[1]` | `[0]` | Single node has no next |