#1019

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Next Greater Node In Linked List

Find the next greater value for each node in a linked list using monotonic stack techniques for efficient traversal.

Problem Statement

Given the head of a singly linked list, determine for each node the first subsequent node that has a strictly larger value. Return the results in an array corresponding to the original node order, using 0 if no such node exists.

You must handle the linked list efficiently without unnecessary repeated traversal. Employ techniques that combine linked list pointer manipulation with array and stack structures to achieve optimal performance for up to 10,000 nodes.

Examples

Example 1

Input: head = [2,1,5]

Output: [5,5,0]

Example details omitted.

Example 2

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

Output: [7,0,5,5,0]

Example details omitted.

Constraints

The number of nodes in the list is n.
1 <= n <= 104
1 <= Node.val <= 109

Solution Approach

Convert Linked List to Array

Iterate through the linked list to create an array of node values, preserving original order. This allows index-based access for easier application of stack-based logic.

Use a Monotonic Stack

Maintain a stack of indices whose next greater value hasn't been found yet. Traverse the array, and for each value, pop indices from the stack when the current value is larger, assigning it as their next greater value.

Populate Remaining Nodes

After traversal, any indices left in the stack do not have a next greater node. Set their corresponding array entries to 0, finalizing the output array.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

Time complexity is O(n) because each node is pushed and popped at most once from the stack. Space complexity is O(n) for storing the array of node values and the stack.

What Interviewers Usually Probe

Expecting use of a monotonic stack to efficiently track next greater elements in a linked list context.
Looking for correct handling of node indexing when mapping linked list to array.
Assessing understanding of linear-time solutions versus naive O(n^2) traversal approaches.

Common Pitfalls or Variants

Common pitfalls

Forgetting to convert the linked list into an array first, which complicates index-based stack management.
Incorrectly popping from the stack too early or late, leading to wrong next greater assignments.
Failing to set remaining nodes to 0 after stack processing, resulting in incomplete output.

Follow-up variants

Finding next smaller node instead of next greater, adjusting stack condition accordingly.
Applying the pattern to a circular linked list where next greater may wrap around to the start.
Handling multiple linked lists simultaneously, requiring separate stacks or merged tracking.

FAQ

What is the most efficient approach for Next Greater Node In Linked List?

Convert the linked list into an array and use a monotonic decreasing stack to track nodes without known next greater values, achieving O(n) time.

Can this pattern be applied to arrays directly?

Yes, the monotonic stack approach works directly on arrays, but mapping from a linked list requires initial conversion to preserve order.

Why do we need a stack for this problem?

The stack tracks nodes whose next greater value hasn’t been determined yet, allowing efficient updates as larger values are encountered.

What happens if a node has no next greater node?

Any node remaining in the stack after full traversal has no next greater node, and its corresponding array entry is set to 0.

How does this solution avoid O(n^2) traversal?

Each node is pushed and popped from the stack at most once, ensuring linear traversal instead of checking every subsequent node for each element.

terminal

Solution

Solution 1: Monotonic Stack

The problem requires finding the next larger node for each node in the linked list, that is, finding the first node to the right of each node in the linked list that is larger than it. We first traverse the linked list and store the values in the linked list in an array $nums$. For each element in the array $nums$, we just need to find the first element to its right that is larger than it. The problem of finding the next larger element can be solved using a monotonic stack.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

# Definition for singly-linked list.
# 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]:
        nums = []
        while head:
            nums.append(head.val)
            head = head.next
        stk = []
        n = len(nums)
        ans = [0] * n
        for i in range(n - 1, -1, -1):
            while stk and stk[-1] <= nums[i]:
                stk.pop()
            if stk:
                ans[i] = stk[-1]
            stk.append(nums[i])
        return ans

Continue Practicing

#1008 construct binary search tree from preorder traversal #975 odd even jump #962 maximum width ramp