Next Greater Node In Linked List - Leetcode Solution

The Next Greater Node In Linked List problem on Leetcode asks us to find the next greater element for each node in a linked list.

We are given a list of integers as input, which represent the values of nodes in the linked list. Our task is to return a list where each element represents the value of the next greater node of the linked list. If there is no greater node, then we should return 0.

For example, let's say we are given the following input:

[2, 7, 4, 3, 5]

This represents the following linked list:

2 -> 7 -> 4 -> 3 -> 5

Our task is to find the next greater node for each of these nodes:

• The next greater node for 2 is 7
• The next greater node for 7 is 0 (since there are no nodes greater than 7)
• The next greater node for 4 is 5
• The next greater node for 3 is 5
• The next greater node for 5 is 0 (since there are no nodes greater than 5)

Therefore, our output should be:

[7, 0, 5, 5, 0]

To solve this problem, we can use a stack. We traverse the given linked list and for each node, we do the following:

1. Pop elements from the stack while the stack is not empty and the top element of the stack is less than the current node's value. For each popped element, we store its next greater value as the current node's value.
2. Push the current node's value onto the stack.

At the end of the traversal, we pop all the remaining elements from the stack and mark their next greater value as 0.

Here's the Python code to implement the above algorithm:

class Solution:
    def nextLargerNodes(self, head: ListNode) -> List[int]:
        stack = []
        res = []
        
        node = head
        while node:
            while stack and stack[-1][1] < node.val:
                _, val = stack.pop()
                res.append(val)
            stack.append((len(res), node.val))
            res.append(0)
            node = node.next
            
        return res[:len(stack)]

Here, we maintain a tuple in the stack where the first element is the index of the node in the linked list, and the second element is the value of the node. This helps us to keep track of the indices of popped nodes and their corresponding next greater values.

Finally, we return the subarray of the res array containing only the next greater values, excluding the extra 0 values added at the end.

The time complexity of this algorithm is O(n), where n is the length of the linked list, since we traverse the linked list only once. The space complexity is also O(n), since we use a stack and a result array of size n.

1