1019. Next Greater Node In Linked List

Problem Description

Given the head of a linked list, find the value of the next greater node for each node. The next greater node for a given node is the first node to its right with a strictly larger value. If no such node exists, the next greater node is 0. Return an array where the i-th element is the value of the next greater node of the i-th node (1-indexed).

Solution: Monotonic Stack

This problem can be efficiently solved using a monotonic stack. A monotonic stack is a stack where the elements are always in increasing or decreasing order. In this case, we'll use a decreasing monotonic stack.

Algorithm:

1. Convert Linked List to Array: First, traverse the linked list and store the node values in an array nums.
2. Initialize Stack and Result Array: Create an empty stack stk and an array ans of the same size as nums, initialized with zeros. ans will store the result.
3. Iterate Backwards: Iterate through nums from right to left (index i from n-1 to 0, where n is the length of nums).
4. Monotonic Stack Processing: For each element nums[i]:
   • While the stack is not empty and the top element of the stack (stk[-1]) is less than or equal to nums[i], pop elements from the stack. This ensures that the stack maintains a decreasing order.
   • If the stack is not empty after popping, the top element of the stack is the next greater node for nums[i]. Assign this value to ans[i].
   • Push nums[i] onto the stack.
5. Return Result: After iterating through all elements, ans contains the next greater node values for each node. Return ans.

Time and Space Complexity

• Time Complexity: O(n), where n is the number of nodes in the linked list. We iterate through the array once. The stack operations (push and pop) take constant time on average.
• Space Complexity: O(n) in the worst case, to store the nums array and the stack. In the best-case scenario where the linked list is already in decreasing order, the stack space would be minimal.

Code Implementation (Python)

class Solution:
    def nextLargerNodes(self, head: ListNode) -> List[int]:
        nums = []
        while head:
            nums.append(head.val)
            head = head.next
        stk = []
        n = len(nums)
        ans = [0] * n
        for i in range(n - 1, -1, -1):
            while stk and stk[-1] <= nums[i]:
                stk.pop()
            if stk:
                ans[i] = stk[-1]
            stk.append(nums[i])
        return ans
 

The code in other languages (Java, C++, Go, TypeScript, Rust, Javascript) follows a very similar structure, adapting the syntax and data structures to each language's specifics, but maintaining the same core algorithm. The fundamental idea of using a decreasing monotonic stack to efficiently find the next greater element remains consistent across all implementations.