Problem

You are given the head of a linked list with n nodes.

For each node in the list, find the value of the next greater node. That is, for each node, find the value of the first node that is next to it and has a strictly larger value than it.

Return an integer array answer where answer[i] is the value of the next greater node of the ith node (1-indexed). If the ith node does not have a next greater node, set answer[i] = 0.

Examples

Example 1

1
2
3
4
5


![](https://assets.leetcode.com/uploads/2021/08/05/linkedlistnext1.jpg)

Input: head = [2,1,5]
Output: [5,5,0]

Example 2

1
2
3
4
5


![](https://assets.leetcode.com/uploads/2021/08/05/linkedlistnext2.jpg)

Input: head = [2,7,4,3,5]
Output: [7,0,5,5,0]

Constraints

  • The number of nodes in the list is n.
  • 1 <= n <= 10^4
  • 1 <= Node.val <= 10^9

Solution

Method 1 -

Intuition

Convert the linked list to an array, then use a monotonic stack to efficiently find the next greater value for each node.

Approach

  1. Traverse the linked list and store values in an array.
  2. Use a stack to keep indices of nodes whose next greater value hasn’t been found yet.
  3. For each value, pop from the stack while the current value is greater than the value at the stack’s top index, and set answer for those indices.
  4. Remaining indices in the stack have no greater value, so their answer is 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

vector<int> nextLargerNodes(ListNode* head) {
    vector<int> vals;
    while (head) { vals.push_back(head->val); head = head->next; }
    vector<int> res(vals.size(), 0);
    stack<int> st;
    for (int i = 0; i < vals.size(); ++i) {
        while (!st.empty() && vals[i] > vals[st.top()]) {
            res[st.top()] = vals[i]; st.pop();
        }
        st.push(i);
    }
    return res;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func nextLargerNodes(head *ListNode) []int {
    vals := []int{}
    for node := head; node != nil; node = node.Next {
        vals = append(vals, node.Val)
    }
    res := make([]int, len(vals))
    st := []int{}
    for i, v := range vals {
        for len(st) > 0 && v > vals[st[len(st)-1]] {
            res[st[len(st)-1]] = v
            st = st[:len(st)-1]
        }
        st = append(st, i)
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

public int[] nextLargerNodes(ListNode head) {
    List<Integer> vals = new ArrayList<>();
    while (head != null) { vals.add(head.val); head = head.next; }
    int[] res = new int[vals.size()];
    Stack<Integer> st = new Stack<>();
    for (int i = 0; i < vals.size(); i++) {
        while (!st.isEmpty() && vals.get(i) > vals.get(st.peek())) {
            res[st.pop()] = vals.get(i);
        }
        st.push(i);
    }
    return res;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

fun nextLargerNodes(head: ListNode?): IntArray {
    val vals = mutableListOf<Int>()
    var node = head
    while (node != null) {
        vals.add(node.`val`)
        node = node.next
    }
    val res = IntArray(vals.size)
    val st = ArrayDeque<Int>()
    for (i in vals.indices) {
        while (st.isNotEmpty() && vals[i] > vals[st.last()]) {
            res[st.removeLast()] = vals[i]
        }
        st.addLast(i)
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def nextLargerNodes(head):
    vals = []
    while head:
        vals.append(head.val)
        head = head.next
    res = [0] * len(vals)
    st = []
    for i, v in enumerate(vals):
        while st and v > vals[st[-1]]:
            res[st.pop()] = v
        st.append(i)
    return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn next_larger_nodes(head: Option<Box<ListNode>>) -> Vec<i32> {
        let mut vals = vec![];
        let mut node = head;
        while let Some(n) = node {
            vals.push(n.val);
            node = n.next;
        }
        let mut res = vec![0; vals.len()];
        let mut st = vec![];
        for (i, &v) in vals.iter().enumerate() {
            while let Some(&j) = st.last() {
                if v > vals[j] {
                    res[j] = v;
                    st.pop();
                } else { break; }
            }
            st.push(i);
        }
        res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

function nextLargerNodes(head: ListNode | null): number[] {
    const vals: number[] = [];
    let node = head;
    while (node) {
        vals.push(node.val);
        node = node.next;
    }
    const res = Array(vals.length).fill(0);
    const st: number[] = [];
    for (let i = 0; i < vals.length; i++) {
        while (st.length && vals[i] > vals[st[st.length-1]]) {
            res[st.pop()!] = vals[i];
        }
        st.push(i);
    }
    return res;
}

Complexity

  • ⏰ Time complexity: O(n) where n is the number of nodes.
  • 🧺 Space complexity: O(n) for the array and stack.