Formatted question description: https://leetcode.ca/all/1019.html

1019. Next Greater Node In Linked List (Medium)

We are given a linked list with head as the first node.  Let's number the nodes in the list: node_1, node_2, node_3, ... etc.

Each node may have a next larger value: for node_i, next_larger(node_i) is the node_j.val such that j > i, node_j.val > node_i.val, and j is the smallest possible choice.  If such a j does not exist, the next larger value is 0.

Return an array of integers answer, where answer[i] = next_larger(node_{i+1}).

Note that in the example inputs (not outputs) below, arrays such as [2,1,5] represent the serialization of a linked list with a head node value of 2, second node value of 1, and third node value of 5.

 

Example 1:

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

Example 2:

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

Example 3:

Input: [1,7,5,1,9,2,5,1]
Output: [7,9,9,9,0,5,0,0]

 

Note:

1. 1 <= node.val <= 10^9 for each node in the linked list.
2. The given list has length in the range [0, 10000].

Companies:
Microsoft

Related Topics:
Linked List, Stack

Solution 1. Monostack

// OJ: https://leetcode.com/problems/next-greater-node-in-linked-list/

// Time: O(N)
// Space: O(N)
class Solution {
    ListNode *reverseList(ListNode *head) {
        ListNode h;
        while (head) {
            auto node = head;
            head = head->next;
            node->next = h.next;
            h.next = node;
        }
        return h.next;
    }
public:
    vector<int> nextLargerNodes(ListNode* head) {
        vector<int> ans;
        stack<int> s;
        head = reverseList(head);
        for (; head; head = head->next) {
            while (s.size() && s.top() <= head->val) s.pop();
            ans.push_back(s.size() ? s.top() : 0);
            s.push(head->val);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

Solution 2. Monostack

// OJ: https://leetcode.com/problems/next-greater-node-in-linked-list/

// Time: O(N)
// Space: O(N)
class Solution {
public:
    vector<int> nextLargerNodes(ListNode* head) {
        vector<int> ans;
        stack<int> s;
        for (; head; head = head->next) ans.push_back(head->val);
        for (int i = 0; i < ans.size(); ++i) {
            while (s.size() && ans[s.top()] < ans[i]) {
                ans[s.top()] = ans[i];
                s.pop();
            }
            s.push(i);
        }
        for (; s.size(); s.pop()) ans[s.top()] = 0;
        return ans;
    }
};

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] nextLargerNodes(ListNode head) {
        Stack<ListNode> nodesStack = new Stack<ListNode>();
        ListNode temp = head;
        while (temp != null) {
            nodesStack.push(temp);
            temp = temp.next;
        }
        int length = nodesStack.size();
        int[] nextLarger = new int[length];
        Stack<Integer> largestStack = new Stack<Integer>();
        for (int i = length - 1; i >= 0; i--) {
            ListNode node = nodesStack.pop();
            int value = node.val;
            while (!largestStack.isEmpty() && largestStack.peek() <= value)
                largestStack.pop();
            if (!largestStack.isEmpty())
                nextLarger[i] = largestStack.peek();
            largestStack.push(value);
        }
        return nextLarger;
    }
}

All Problems

All Solutions