Next Greater Node In Linked List

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<sup>th</sup> node (1-indexed). If the i<sup>th</sup> node does not have a next greater node, set answer[i] = 0.

Example 1: Input: head = [2,1,5] Output: [5,5,0]

Example 2: Input: head = [2,7,4,3,5] Output: [7,0,5,5,0]

Constraints: The number of nodes in the list is n. 1 <= n <= 10^4 1 <= Node.val <= 10^9

# 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]:
        # Convert linked list to array
        A = []
        curr = head
        while curr:
            A.append(curr.val)
            curr = curr.next
        
        n = len(A)
        ans = [0] * n
        stack = [] # Monotonic decreasing stack
        
        for i in range(n):
            # While the stack is not empty and the current element is greater than the top of the stack
            while stack and A[i] > A[stack[-1]]:
                # Pop the top of the stack and set the answer for that index to the current element
                ans[stack.pop()] = A[i]
            # Push the current index onto the stack
            stack.append(i)
        
        return ans

Explanation:

1. Convert Linked List to Array: The linked list is traversed, and the value of each node is appended to an array A. This makes it easier to access elements by index.
2. Initialize Answer Array and Stack:
   • ans: An array of the same length as A, initialized with zeros. This array will store the next greater node for each element.
   • stack: A stack to store indices of elements in A. This stack is used to maintain a decreasing order of elements.
3. Iterate Through the Array:
   • The code iterates through the array A using a for loop.
   • Monotonic Decreasing Stack: The stack maintains a decreasing order of elements. This means that for any two indices i and j in the stack, if i is below j in the stack, then A[i] >= A[j].
   • Finding Next Greater Node:
     • While the stack is not empty and the current element A[i] is greater than the element at the index on the top of the stack (A[stack[-1]]), it means that A[i] is the next greater node for the element at the index on the top of the stack.
     • The index on the top of the stack is popped, and the corresponding value in the ans array is updated to A[i].
   • Pushing to the Stack: The index i is pushed onto the stack to maintain the decreasing order.
4. Return Answer Array: The ans array, containing the next greater node for each element in the linked list, is returned.

Example:

Let's walk through an example with the input head = [2, 1, 5].

1. Convert to Array: A = [2, 1, 5]
2. Initialization: ans = [0, 0, 0], stack = []
3. Iteration:
   • i = 0, A[i] = 2. Stack is empty, so push 0 onto the stack. stack = [0]
   • i = 1, A[i] = 1. A[i] < A[stack[-1]] (1 < 2), so push 1 onto the stack. stack = [0, 1]
   • i = 2, A[i] = 5. A[i] > A[stack[-1]] (5 > 1), so pop 1 from the stack and set ans[1] = 5. stack = [0]. Now A[i] > A[stack[-1]] (5 > 2), so pop 0 from the stack and set ans[0] = 5. stack = []. Push 2 onto the stack. stack = [2]
4. Return: ans = [5, 5, 0]

Big O Analysis:

• Time Complexity: O(n), where n is the number of nodes in the linked list. This is because we iterate through the linked list once to convert it to an array, and then iterate through the array once to find the next greater node for each element.
• Space Complexity: O(n), where n is the number of nodes in the linked list. This is because we store the linked list in an array, and we use a stack to store the indices of the elements in the array.