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 <stdio.h>
2#include <stdlib.h>
3
4// Definition for singly-linked list.
5struct ListNode {
6 int val;
7 struct ListNode *next;
8};
9
10struct ListNode** createStack(int n) {
11 return (struct ListNode**)malloc(n * sizeof(struct ListNode*));
12}
13
14int* nextLargerNodes(struct ListNode* head, int* returnSize) {
15 int *results = (int*)malloc(10000 * sizeof(int));
16 struct ListNode **stack = createStack(10000);
17 int *stackIndex = (int*)malloc(10000 * sizeof(int));
18 int top = -1, index = 0;
19 struct ListNode *current = head;
20
21 while (current) {
22 while (top >= 0 && stack[top]->val < current->val) {
23 results[stackIndex[top--]] = current->val;
24 }
25 stack[++top] = current;
26 stackIndex[top] = index;
27 results[index++] = 0;
28 current = current->next;
29 }
30 *returnSize = index;
31 return results;
32}
33This C solution uses an array-based stack to capture and process nodes from the linked list. As each node is encountered, it checks the stack for any nodes smaller than the current node. If found, it updates the result set. The code is efficient and operates in O(n) time complexity.
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.