Next Greater Node In Linked List

Quick Links

Code Solution


class Solution:
  def nextLargerNodes(self, head: ListNode) -> list[int]:
    ans = []
    stack = []

    while head:
      while stack and head.val > ans[stack[-1]]:
        index = stack.pop()
        ans[index] = head.val
      stack.append(len(ans))
      ans.append(head.val)
      head = head.next

    for i in stack:
      ans[i] = 0

    return ans

Problem Description

So, you’ve got a linked list, and you’re wondering, “Where’s the next greater node?” It’s like being at a party and trying to find someone taller than you in a sea of people. Spoiler alert: it’s not always easy!

In this problem, you’re given a linked list where each node contains a value. Your mission, should you choose to accept it, is to find the next node that has a greater value for each node in the list. If there’s no greater value, just return 0. It’s like asking your friends to find someone taller than you, and if they can’t, they just shrug and say, “Sorry, buddy!”

Approach

The code uses a stack to keep track of the indices of the nodes whose next greater values we are still searching for. As we traverse the linked list, we compare the current node’s value with the values at the indices stored in the stack. If the current value is greater, we pop from the stack and update the answer list with the current value. If we finish traversing the list and still have indices left in the stack, we set those indices to 0, indicating no greater value was found.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n), where n is the number of nodes in the linked list. Each node is processed once.
Space Complexity	O(n) in the worst case for the stack and the answer list.

Real-World Example

Imagine you’re at a concert, and you’re trying to find someone who can see over the crowd. You’re standing there, and every time someone taller walks by, you’re like, “Finally, someone who can see the stage!” But if no one taller comes along, you’re left staring at the same view. This is exactly what the algorithm does: it looks for the next taller person (or node) and keeps track of those who are still waiting for their moment to shine.