Sponsored
Sponsored
This approach leverages a monotonic stack to efficiently find the next greater element for each node in the linked list. By traversing the linked list once, we can maintain a stack to track potentially greater nodes and update results as we traverse.
Time Complexity: O(n), where n is the length of the linked list, because each node is pushed and popped from the stack at most once.
Space Complexity: O(n), needed for storing the result and stack.
1#include <vector>
2#include <stack>
3
4struct ListNode {
5 int val;
6 ListNode *next;
7 ListNode(int x) : val(x), next(NULL) {}
8};
9
10std::vector<int> nextLargerNodes(ListNode* head) {
11 std::vector<int> result;
12 std::stack<std::pair<int, int>> s;
13 ListNode* current = head;
14
15 int index = 0;
16 while (current) {
17 while (!s.empty() && s.top().first < current->val) {
18 result[s.top().second] = current->val;
19 s.pop();
20 }
21 s.push({current->val, index});
22 result.push_back(0);
23 current = current->next;
24 index++;
25 }
26 return result;
27}In this C++ solution, a stack is used to efficiently manage the indices and values of the nodes. Elements are processed in a pass over the linked list, updating entries as greater elements are found.
In this approach, reverse the linked list initially and then traverse, keeping track of the next greatest node using a stack. As this traversal is reversed, use a stack to efficiently find and keep the nearest greatest value.
Time Complexity: O(n)
Space Complexity: O(n)
1
In this approach, the linked list is reversed first. As we traverse from the new start, greater elements are stacked and compared for finding the next greater node. At the end, a final reversal of results provides the answer.