Next Greater Node In Linked List

Problem Id: 1019 Difficulty: Medium Tag: Linked List Tag: Stack


Intuition

First, we need to reverse the original linked list. Then, we could get the next greater nodes in the reverse order. For each node, we only need to keep greater node after it. For those who are smaller than the current and is after the node, they could be ignored.

Solution


# 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]:
        head = self._reverse(head)
        stack = []
        next_greater_reverse = []
        current = head
        while current:
            while stack and stack[-1] <= current.val:
                stack.pop()
            if not stack:
                next_greater_reverse.append(0)
            else:
                next_greater_reverse.append(stack[-1])
            stack.append(current.val)
            current = current.next
        return next_greater_reverse[::-1]

    def _reverse(self, head):
        current = head
        parent = None
        while current:
            tmp = current.next
            current.next = parent
            parent = current
            current = tmp
        return parent