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 corresponds to the -th node in the original linked list order.
Inputs & Outputs:
- Input: A singly-linked list (
head) with values up to . Length range[0, 10000]. - Output: An integer array
answerof length equal to the number of nodes in the linked list.
Constraints & Edge Cases:
- List can be empty (
headisNone). Return an empty array immediately if so. - Values are positive integers (). 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 , 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:
- 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.
- Since duplicates are allowed but strict inequality () is required, equal values will not trigger a pop (the condition
stack_top < currenthandles this).
Because linked lists do not support random access by index efficiently without traversal, we first convert the list into an array to allow indexing for our stack logic. This conversion takes one pass (), and then the stack operations take another linear pass overall.
Approach
- 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 ifheadisNone. - Initialize: Create a result list
ansof size equal tolen(nums), initialized with zeros (representing “no next larger found”). Initialize an empty stack to store indices. - 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
ionto the stack to wait for a future larger value.
- While the stack is not empty AND the current value (
- Return: Return the populated
ansarray. Elements remaining in the stack at the end correspond to nodes with no next larger element, which remain as their default initialization of0.
Complexity Analysis
- Time Complexity: . We traverse the linked list once ( 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: for storing the converted array
nums, the result arrayansof size , and the monotonic stack which holds at most indices.
Edge Cases Handled
- Empty List (
head = None): The function checks this immediately and returns an empty list[]. This prevents index errors during traversal. - 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. - Strict Inequality (Duplicates): The condition
nums[stack[-1]] < valensures 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 ( and ). - Large Values: Python integers handle arbitrary size, so inputs up to 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