Next Greater Node In Linked List

class Solution {
public:
    vector<int> findNextGreaterElements(ListNode* start) {
        vector<int> results;
        //Stack holds pairs of index and node value
        vector<pair<int, int>> stack;
        int index = 0;
    
        while(start != nullptr) {
            // Set the default next greater to 0
            results.push_back(0);
            while(stack.size() && start->val > stack.back().second) {
                auto [pos, value] = stack.back();
                stack.pop_back();
                results[pos] = start->val;
            }
            // Record the index and the value in the stack
            stack.push_back({index++, start->val});
            start = start->next;
        }
        return results;
    }
};

The solution for finding the next greater node in a linked list in C++ leverages the use of a vector to store results and another vector to act as a stack for keeping track of indices and node values. Here's how the solution functions:

• Create a results vector to store the result for each node, initialized with zeros implying no next greater element found.
• Use a stack vector, effectively behaving as a stack, to keep track of node values and their respective indices as one traverses the list.
• For each node in the linked list:
  • If the stack isn't empty and the current node's value exceeds the value of the node at the top of the stack (stack.back().second):
    • Extract the position and value from the top of the stack.
    • Empty the stack until a node with a greater or equal value is found or the stack becomes empty.
    • Update the result for the popped node's index with the current node's value.
  • Push the current index and node value onto the stack.
  • Move to the next node in the list.

In the end, return the results vector, where each entry at index i contains the value of the next greater node for the node at index i in the linked list, or 0 if no such node exists. This solution efficiently finds the next greater node for each element in the linked list in a single pass, using the stack to track and update results as greater nodes are encountered.

class Solution {
    public int[] findNextGreater(ListNode node) {
        ArrayList<Integer> results = new ArrayList<>();
        Stack<int[]> valueStack = new Stack<>();
        // Index to track position
        int index = 0;
    
        while (node != null) {
            // Initialize the next greater element as 0
            results.add(0);
            while (!valueStack.isEmpty() && node.val > valueStack.peek()[1]) {
                int[] topElem = valueStack.pop();
                results.set(topElem[0], node.val);
            }
            // Push current value and its index
            valueStack.push(new int[]{index++, node.val});
            node = node.next;
        }
        
        return results.stream().mapToInt(i -> i).toArray();
    }
}

This solution focuses on solving the problem of finding the next greater node in a linked list using Java. It efficiently determines the next greater node's value for each node in the linked list and returns these values in an array.

Here's the approach the code takes:

1. Utilize an ArrayList called results to store the results where the initial assumption for each node's next greater value is zero.

2. Use a Stack to track values and their indices as they process through the linked list. The stack helps in determining the next greater node for the elements efficiently.

3. Traverse through each node of the linked list. Within this loop:

   • Compare the current node’s value against the top element of the stack:

     • If the current node's value is greater than the top element of the stacked value, keep popping from the stack and update the corresponding index in the results list with the current node's value.

   • Push each node value along with the current index onto the stack as an array [index, nodeValue]. Increase the index for the next iteration.

4. After finishing the traversal, convert the ArrayList to an array of integers and return.

The use of a stack and list ensures an optimal solution allowing each node to be processed in a linear traversal of the list. By leveraging the stack's Last In, First Out (LIFO) property, the solution checks for greater values in an efficient manner, achieving significant time savings for larger inputs.

# Definition of linked list node.
# class ListNode:
#     def __init__(self, value=0, next_node=None):
#         self.val = value
#         self.next = next_node
    
class Solution:
    def nextLargerElements(self, head: ListNode) -> List[int]:
        result, stk = [], []
        # Index variable 'index' used for positioning in the result list.
        index = 0
            
        while head:
            # Initialize the greater elements list with 0.
            result.append(0)
            while stk and head.val > stk[-1][1]:
                idx, value = stk.pop()
                result[idx] = head.val
    
            # Push current index and value of node into stack.
            stk.append([index, head.val])
            index += 1
            head = head.next
            
        return result

The Python program provided defines a solution to finding the next greater node in a linked list where, for each node, you aim to find the subsequent node's value which is greater than the current node's value. Below is an outline of how the solution works:

• A class named Solution is defined with a method nextLargerElements which takes head of a linked list as an argument.
• Two lists, result and stk (used as a stack), are initialized. result stores the final output where each element corresponds to the next larger value for each node in the linked list. If no larger value exists, the position is set to 0.
• A while loop iterates over the linked list. During each iteration:
  • The current node value is compared with the last element’s value stored in the stk.
  • If the current node value is greater, it indicates the next larger element for the node corresponding to the stack's top index. This value is then popped from the stk, and the current node's value replaces 0 in the result list at the corresponding index.
  • Regardless of whether the current node's value is greater or not, the current node index and value are pushed onto stk.
  • The index is then incremented, and the loop moves to the next node.
• Once all nodes are visited, the loop terminates, and result is returned with the next greater elements for each node. If no greater element is found for a node, it remains 0 as initialized.

This approach efficiently determines the next greater node using a stack data structure to keep track of nodes which need the next greater number to be resolved, and it gets solved in a single pass through the linked list. The stack helps in reducing the complexity of comparing every node with every other node, turning the process to linear time complexity with respect to the number of nodes in the list.