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 <= node.val <= 10^9 for each node in the linked list.
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;
    }
};

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

############

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int[] nextLargerNodes(ListNode head) {
        List<Integer> nums = new ArrayList<>();
        for (; head != null; head = head.next) {
            nums.add(head.val);
        }
        Deque<Integer> stk = new ArrayDeque<>();
        int n = nums.size();
        int[] ans = new int[n];
        for (int i = n - 1; i >= 0; --i) {
            while (!stk.isEmpty() && stk.peek() <= nums.get(i)) {
                stk.pop();
            }
            if (!stk.isEmpty()) {
                ans[i] = stk.peek();
            }
            stk.push(nums.get(i));
        }
        return ans;
    }
}

// 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:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution:
    def nextLargerNodes(self, head: ListNode) -> List[int]:
        nums = []
        while head:
            nums.append(head.val)
            head = head.next
        s = []
        larger = [0] * len(nums)
        for i, num in enumerate(nums):
            while s and nums[s[-1]] < num:
                larger[s.pop()] = num
            s.append(i)
        return larger

############

# 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

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func nextLargerNodes(head *ListNode) []int {
	nums := []int{}
	for ; head != nil; head = head.Next {
		nums = append(nums, head.Val)
	}
	stk := []int{}
	n := len(nums)
	ans := make([]int, n)
	for i := n - 1; i >= 0; i-- {
		for len(stk) > 0 && stk[len(stk)-1] <= nums[i] {
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			ans[i] = stk[len(stk)-1]
		}
		stk = append(stk, nums[i])
	}
	return ans
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

interface Item {
    index: number;
    val: number;
}

function nextLargerNodes(head: ListNode | null): number[] {
    const res: number[] = [];
    const stack: Item[] = [];
    let cur = head;
    for (let i = 0; cur != null; i++) {
        res.push(0);
        const { val, next } = cur;
        while (stack.length !== 0 && stack[stack.length - 1].val < val) {
            res[stack.pop().index] = val;
        }
        stack.push({
            val,
            index: i,
        });
        cur = next;
    }
    return res;
}

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {number[]}
 */
var nextLargerNodes = function (head) {
    let nums = [];
    while (head != null) {
        nums.push(head.val);
        head = head.next;
    }
    const n = nums.length;
    let larger = new Array(n).fill(0);
    let stack = [];
    for (let i = 0; i < n; i++) {
        let num = nums[i];
        while (stack.length > 0 && nums[stack[stack.length - 1]] < num) {
            larger[stack.pop()] = num;
        }
        stack.push(i);
    }
    return larger;
};

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
struct Item {
    index: usize,
    val: i32,
}

impl Solution {
    pub fn next_larger_nodes(head: Option<Box<ListNode>>) -> Vec<i32> {
        let mut res = Vec::new();
        let mut stack: Vec<Item> = Vec::new();
        let mut cur = &head;
        for i in 0..usize::MAX {
            if cur.is_none() {
                break;
            }
            res.push(0);
            let node = cur.as_ref().unwrap();
            while !stack.is_empty() && stack.last().unwrap().val < node.val {
                res[stack.pop().unwrap().index] = node.val;
            }
            stack.push(Item {
                index: i,
                val: node.val,
            });
            cur = &node.next;
        }
        res
    }
}

1019 - Next Greater Node In Linked List

1019. Next Greater Node In Linked List (Medium)

Solution 1. Monostack

Solution 2. Monostack

All Problems

All Solutions

Welcome to Subscribe On Youtube

1019. Next Greater Node In Linked List (Medium)

Solution 1. Monostack

Solution 2. Monostack

All Problems

All Solutions