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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Next Greater Node In Linked List

Difficulty: Medium

Problem Description

You are given the head of a linked list with n nodes. For each node in the list, find the value of the next greater node. That is, for each node, find the value of the first node that is next to it and has a strictly larger value than it. Return an integer array answer where answer[i] is the value of the next greater node of the i-th node (1-indexed). If the i-th node does not have a next greater node, set answer[i] = 0.

Key Insights

  • Each node needs to be compared with the subsequent nodes to find the next greater value.
  • A monotonic stack can help efficiently track the nodes and their values as we traverse the list.
  • By maintaining a stack of indices, we can easily find the next greater element for each node in one pass.

Space and Time Complexity

Time Complexity: O(n) - We traverse the linked list and each node is pushed and popped from the stack at most once. Space Complexity: O(n) - The stack may store all nodes in the worst case.

Solution

The problem can be solved using a monotonic stack. The algorithm involves traversing the linked list while maintaining a stack to store the indices of the nodes. As we process each node, we check if it is greater than the node at the index stored at the top of the stack. If it is, we pop the index from the stack and set the corresponding answer value to the current node's value. This continues until the stack is empty or the current node is not greater. Finally, if there are any indices left in the stack, they will not have a next greater node, and their values will remain zero.

Code Solutions

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

def nextLargerNodes(head: ListNode):
    # Convert the linked list to an array for easy access by index
    values = []
    while head:
        values.append(head.val)
        head = head.next

    n = len(values)
    answer = [0] * n
    stack = []

    for i in range(n):
        # While stack is not empty and the current value is greater than
        # the value at the index stored at the top of the stack
        while stack and values[i] > values[stack[-1]]:
            index = stack.pop()
            answer[index] = values[i]
        stack.append(i)

    return answer
← Back to All Questions