We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Next Greater Node In Linked List

Number: 1072

Difficulty: Medium

Paid? No

Companies: Amazon, Microsoft

Problem Description

Given the head of a linked list, for each node, determine the value of the first node that follows it and has a strictly larger value. If such a node does not exist, use 0. The answer is returned as an array where the position corresponds to the 1-indexed position of the node.

Key Insights

  • Convert the linked list into an array for easier index manipulation.
  • Use a monotonic (decreasing) stack to store indices of nodes that haven't found their next greater element.
  • As you traverse the array, compare the current value with values corresponding to indices stored in the stack.
  • When the current value is larger, update the result for those indices and pop them off the stack.
  • Unresolved indices in the stack will have a next greater value of 0.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

The solution begins by converting the linked list into an array, which allows for straightforward index-based traversal. A stack is used to keep track of indices for which we have not yet found a next greater element. As we iterate through the array, if the current element's value is greater than the value at the index on the top of the stack, it means the current element is the next greater element for that index. We update the result at that index and pop it from the stack. This process continues until the stack is either empty or the current element is not greater than the element referenced by the stack's top index. Finally, any indices remaining in the stack are assigned a value of 0 as there is no greater element after them.

Code Solutions

# 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: ListNode) -> list:
        # Convert linked list to array for easy access by index.
        values = []
        current = head
        while current:
            values.append(current.val)
            current = current.next
        
        # Initialize result array with zeros.
        result = [0] * len(values)
        stack = []  # Stack to store indices of nodes.
        
        # Iterate through the list using the monotonic stack approach.
        for i, value in enumerate(values):
            # Find all nodes in the stack that have a lesser value than the current node.
            while stack and values[stack[-1]] < value:
                index = stack.pop()
                result[index] = value
            stack.append(i)
        
        return result
← Back to All Questions