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

• Java
• C++
• Python

• /**
   * 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;
      }
  }
  

• // 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;
      }
  };
  

• # Definition for singly-linked list.
  # class ListNode(object):
  #     def __init__(self, x):
  #         self.val = x
  #         self.next = None
  
  class Solution(object):
      def nextLargerNodes(self, head):
          """
          :type head: ListNode
          :rtype: List[int]
          """
          nums = []
          while head:
              nums.append(head.val)
              head = head.next
          stack = []
          res = [0] * len(nums)
          for i, n in enumerate(nums):
              while stack and nums[stack[-1]] < n:
                  res[stack.pop()] = n
              stack.append(i)
          return res
  

All Problems

All Solutions