Next Greater Node In Linked List

1. Convert the input linked list into an ArrayList of integers to facilitate easy access to elements by index.
2. Get the size n of the list.
3. Initialize an integer array answer of size n with all elements set to 0.
4. Iterate through the ArrayList with an index i from 0 to n-1.
5. For each i, start a nested inner loop with index j from i+1 to n-1.
6. Inside the inner loop, if the element at index j is strictly greater than the element at index i, it means we have found the next greater node.
7. Set answer[i] to the value of this greater element (list.get(j)) and immediately break the inner loop, as we only need the first greater node.
8. If the inner loop completes without finding any greater element, answer[i] remains 0.
9. After the outer loop finishes, return the answer array.

The brute-force method is the most intuitive way to solve the problem. The core idea is to check every possible pair of nodes (i, j) where node j appears after node i.

To make the implementation simpler, we first traverse the linked list and store all its node values in a dynamic array, like an ArrayList in Java. This conversion allows us to use indices, which is more convenient than using pointers for this specific logic.

Once we have the values in an array, we create a result array answer of the same size, initialized to all zeros. Then, we use a pair of nested loops. The outer loop picks an element, and the inner loop scans the rest of the array to its right to find the first element that is larger than the one picked by the outer loop. When a larger element is found, we record its value in our answer array and break the inner loop to proceed to the next element in the outer loop. If the inner loop finishes without finding a greater element, the default value of 0 remains, which correctly signifies that no next greater node exists.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11import java.util.ArrayList;12import java.util.List;13 14class Solution {15    public int[] nextLargerNodes(ListNode head) {16        // Convert linked list to an ArrayList for easier access.17        List<Integer> list = new ArrayList<>();18        for (ListNode node = head; node != null; node = node.next) {19            list.add(node.val);20        }21        22        int n = list.size();23        int[] answer = new int[n];24        25        // Use nested loops to find the next greater node.26        for (int i = 0; i < n; i++) {27            for (int j = i + 1; j < n; j++) {28                if (list.get(j) > list.get(i)) {29                    answer[i] = list.get(j);30                    break; // Found the first greater node, so we can stop searching.31                }32            }33            // If no greater node is found, answer[i] remains 0 by default.34        }35        36        return answer;37    }38}

1. Reverse the Linked List & Count Nodes: Traverse the linked list to reverse it in-place. During this traversal, count the number of nodes, n.
2. Initialize: Create an integer array answer of size n and an empty Stack<Integer>.
3. Traverse Reversed List: Iterate through the reversed list, starting from its new head. Maintain an index pointer, i, starting from n-1 and decrementing in each step.
4. Use Monotonic Stack: For each node curr in the reversed list: a. While the stack is not empty and the value at the top of the stack is less than or equal to the current node's value (stack.peek() <= curr.val), pop from the stack. This removes all elements that cannot be the next greater element for curr or any subsequent nodes in the original list. b. After the while loop, if the stack is empty, it means no greater element exists to its right (in the original list). Set answer[i] = 0. c. Otherwise, the value at the top of the stack (stack.peek()) is the first greater element. Set answer[i] = stack.peek(). d. Push the current node's value (curr.val) onto the stack. e. Decrement the index i.
5. Return Result: After iterating through the entire reversed list, the answer array is correctly populated. Return it.

This optimal solution cleverly reframes the problem. Instead of searching forward for a "next greater node," we can reverse the list and search for a "previous greater node" relative to the reversed sequence. This is a classic problem pattern solvable efficiently with a monotonic stack.

The algorithm works as follows: First, we reverse the linked list. This can be done iteratively with O(1) extra space. While reversing, we also count the number of nodes, n, which allows us to create the final answer array of the correct size upfront.

Next, we iterate through this reversed list. We use a stack that we'll maintain in a monotonically decreasing order. For each node we visit, we pop elements from the stack as long as they are less than or equal to the current node's value. The reason for this is that if the current node's value is greater, any of these smaller popped elements can never be the "next greater node" for any of the nodes that came before the current one (in the original list's order).

After popping, the element at the top of the stack (if any) is the first element we've encountered (from right to left in the original list) that is greater than the current node. This is exactly the next greater node. If the stack is empty, no such node exists. We store this result in our answer array. Since we are iterating through the reversed list, we fill the answer array from back to front to maintain the correct order.

Finally, we push the current node's value onto the stack to be a potential "next greater node" for the elements we will visit next.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11import java.util.Stack;12 13class Solution {14    public int[] nextLargerNodes(ListNode head) {15        // Step 1: Reverse the linked list and count its size.16        ListNode prev = null;17        ListNode curr = head;18        int n = 0;19        while (curr != null) {20            ListNode nextTemp = curr.next;21            curr.next = prev;22            prev = curr;23            curr = nextTemp;24            n++;25        }26        ListNode revHead = prev;27        28        // Step 2: Initialize result array and stack.29        int[] answer = new int[n];30        Stack<Integer> stack = new Stack<>();31        int index = n - 1;32        33        // Step 3 & 4: Traverse the reversed list and use the monotonic stack.34        curr = revHead;35        while (curr != null) {36            // Pop elements from stack smaller than or equal to current value.37            while (!stack.isEmpty() && stack.peek() <= curr.val) {38                stack.pop();39            }40            41            // The top of the stack is the next greater element.42            if (stack.isEmpty()) {43                answer[index] = 0;44            } else {45                answer[index] = stack.peek();46            }47            48            // Push current value onto stack for future comparisons.49            stack.push(curr.val);50            51            curr = curr.next;52            index--;53        }54        55        return answer;56    }57}