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)
1public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
private ListNode ReverseList(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
public int[] NextLargerNodes(ListNode head) {
head = ReverseList(head);
Stack<int> stack = new Stack<int>();
List<int> result = new List<int>();
while (head != null) {
while (stack.Count > 0 && stack.Peek() <= head.val)
stack.Pop();
result.Add(stack.Count == 0 ? 0 : stack.Peek());
stack.Push(head.val);
head = head.next;
}
result.Reverse();
return result.ToArray();
}
}This C# solution illustrates reversing the list and using a stack to manage and track next greater nodes. After solving, it reverses results for output.