Next Greater Node In Linked List
Problem
Return an array answer where answer[i] is the value of the next node with strictly greater value (0 if none).
head = [2,1,5][5,5,0]def nextLargerNodes(head):
a = []
cur = head
while cur: a.append(cur.val); cur = cur.next
res = [0] * len(a)
st = []
for i, x in enumerate(a):
while st and a[st[-1]] < x:
res[st.pop()] = x
st.append(i)
return resfunction nextLargerNodes(head) {
const a = [];
for (let cur = head; cur; cur = cur.next) a.push(cur.val);
const res = new Array(a.length).fill(0);
const st = [];
for (let i = 0; i < a.length; i++) {
while (st.length && a[st[st.length - 1]] < a[i]) res[st.pop()] = a[i];
st.push(i);
}
return res;
}class Solution {
public int[] nextLargerNodes(ListNode head) {
List<Integer> a = new ArrayList<>();
for (ListNode c = head; c != null; c = c.next) a.add(c.val);
int[] res = new int[a.size()];
Deque<Integer> st = new ArrayDeque<>();
for (int i = 0; i < a.size(); i++) {
while (!st.isEmpty() && a.get(st.peek()) < a.get(i)) res[st.pop()] = a.get(i);
st.push(i);
}
return res;
}
}vector<int> nextLargerNodes(ListNode* head) {
vector<int> a;
for (auto c = head; c; c = c->next) a.push_back(c->val);
vector<int> res(a.size(), 0);
stack<int> st;
for (int i = 0; i < (int)a.size(); i++) {
while (!st.empty() && a[st.top()] < a[i]) { res[st.top()] = a[i]; st.pop(); }
st.push(i);
}
return res;
}Explanation
A linked list is awkward to look ahead in, so the first step is to simply flatten it into an array a by walking the nodes. After that, this becomes the standard "next greater element" problem on an array.
We scan a left-to-right with a monotonic stack of indices for nodes still waiting for a larger value to appear, kept in decreasing order of value.
When the current value a[i] is greater than the value at the top index, that top finally found its next greater node: we pop it and set res[popped] = a[i]. We keep popping all smaller waiting indices, then push i.
Any index still on the stack at the end has no greater node ahead, so it keeps its default 0.
Example: head = [2, 1, 5] flattens to [2, 1, 5]. The 5 resolves both 2 and 1 to 5, while 5 itself finds nothing, giving [5, 5, 0].