Domain 2MediumMEDIUM

Next Greater Node In Linked List

Converts linked list to array and uses a monotonic stack to find next greater elements efficiently in O(N) time.

Domain: medium•Updated: 2026-09-06
#monotonic_stack#linked_list#O(N)#stack

Problem Breakdown

Goal: For every node in the input singly-linked list, determine the value of the first subsequent node that is strictly larger. If no such node exists (i.e., all remaining nodes are smaller or equal), return 0. The result must be returned as an integer array where index ii corresponds to the (i+1)(i+1)-th node in the original linked list order.

Inputs & Outputs:

  • Input: A singly-linked list (head) with values up to 10910^9. Length range [0, 10000].
  • Output: An integer array answer of length equal to the number of nodes in the linked list.

Constraints & Edge Cases:

  • List can be empty (head is None). Return an empty array immediately if so.
  • Values are positive integers (1≤val1 \le val). No negative numbers or overflow issues for standard 64-bit integers (Python handles large ints automatically).
  • Duplicates: The problem requires strictly greater values (>>). A node with the same value as a previous one does not count as “next larger”.

Intuition

This is an adaptation of the classic Next Greater Element problem, typically solved on arrays. Since we need to find the first element to the right that satisfies valcurrent>valtargetval_{current} > val_{target}, a Monotonic Stack is optimal.

The stack will store indices (or values) of nodes for which we haven’t yet found their next larger value. As we traverse forward:

  1. If the current node’s value is greater than the value at the index on top of our stack, it means we have found the “next larger” element for that stored index. We pop from the stack and record the answer.
  2. Since duplicates are allowed but strict inequality (>>) is required, equal values will not trigger a pop (the condition stack_top < current handles this).

Because linked lists do not support random access by index efficiently without traversal, we first convert the list into an array to allow O(1)O(1) indexing for our stack logic. This conversion takes one pass (O(N)O(N)), and then the stack operations take another linear pass overall.

Approach

  1. Convert: Traverse the linked list once using a pointer curr. Store each node’s value in a Python list (nums). Handle the empty list case immediately by returning an empty array if head is None.
  2. Initialize: Create a result list ans of size equal to len(nums), initialized with zeros (representing “no next larger found”). Initialize an empty stack to store indices.
  3. Traverse & Pop: Iterate through the array using index i:
    • While the stack is not empty AND the current value (nums[i]) is strictly greater than the value at the top of the stack (nums[stack[-1]]):
      • The element on the stack has found its next larger neighbor.
      • Pop the index from the stack and assign ans[popped_index] = nums[i].
    • Push current index i onto the stack to wait for a future larger value.
  4. Return: Return the populated ans array. Elements remaining in the stack at the end correspond to nodes with no next larger element, which remain as their default initialization of 0.

Complexity Analysis

  • Time Complexity: O(N)O(N). We traverse the linked list once (NN steps). The second pass over the values involves iterating through each index exactly twice (once pushed onto stack, once popped or remaining until end). Total operations are linear.
  • Space Complexity: O(N)O(N) for storing the converted array nums, the result array ans of size NN, and the monotonic stack which holds at most NN indices.

Edge Cases Handled

  1. Empty List (head = None): The function checks this immediately and returns an empty list []. This prevents index errors during traversal.
  2. Single Element: If only one node exists, the loop runs once, pushes its index onto the stack, then finishes. No pop occurs because there are no subsequent elements. Result is [0], which is correct as there is no next larger value.
  3. Strict Inequality (Duplicates): The condition nums[stack[-1]] < val ensures that if a duplicate value appears later in the list, it does not trigger a pop for previous duplicates. Only strictly greater values are recorded. This aligns with problem requirements (j>ij > i and nodej.val>nodei.valnode_j.val > node_i.val).
  4. Large Values: Python integers handle arbitrary size, so inputs up to 10910^9 do not cause overflow issues or require special handling beyond standard arithmetic operations.

Solution

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

def nextLargerNodes(head):
    # Handle empty list edge case immediately
    if not head:
        return []
    
    # Step 1: Convert Linked List to array for O(1) indexing access.
    nums = []
    curr = head
    
    # Traverse LL once to build values list
    while curr:
        nums.append(curr.val)
        curr = curr.next
        
    n = len(nums)
    ans = [0] * n
    stack = [] 
    
    # Step 2 & 3: Monotonic Stack logic on indices.
    for i, val in enumerate(nums):
        while stack and nums[stack[-1]] < val:
            idx = stack.pop()
            ans[idx] = val
        
        stack.append(i)
        
    return ans