Problem Statement in English

You are given a linked list of integers.

Your task is to find the next greater node for each node in the linked list, and return a list of values representing the next greater value for each node in the linked list.

Approach

This is a classic problem that can be solved using a monotonic stack.

Here’s how we go about it:

  • We first need to find the length of the linked list. This is done by traversing the linked list and counting the number of nodes.

  • We will be pushing node indices to the stack.

  • We will be popping from the stack when we find a node that is greater than the node at the top of the stack.

    • When we pop from the stack, it means we have found the next greater node for the node at the top of the stack.

    • So we set the answer for that index in our result array with the value of the current node.

  • Push the current node index and value to the stack once all elements below it in the stack are greater than it.

  • Repeat.

Solution in Python


# 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]:
        l = 0

        temp = head
        while temp:
            temp = temp.next
            l += 1

        stack = []
        res = [0] * l

        temp = head

        i = 0
        while temp:
            while stack and stack[-1][1] < temp.val:
                res[stack[-1][0]] = temp.val
                stack.pop()
            stack.append((i, temp.val))
            i += 1
            temp = temp.next

        return res

Complexity

  • Time: $O(n)$
    Where $n$ is the number of nodes in the linked list.

  • Space: $O(n)$
    Since we store the indices of the nodes in the stack.

And we are done.