The O(n) Club: Next Greater Node in a Linked List—Stack Sorcery, Java Edition

The O(n) Club: Next Greater Node in a Linked List—Stack Sorcery, Java Edition

⚡ TL;DR

Every node in your singly linked list wants to know, “Is someone ahead of me actually greater, or am I peaking early?”
Brute force does two dumb loops, torching performance and patience. Modern devs convert the list to an array, bless it with a stack, and enjoy O(n) efficiency. Here, serve yourself some Java:

public int[] nextLargerNodes(ListNode head) {
    List
<integer> values = new ArrayList<>();
    while (head != null) {
        values.add(head.val);
        head = head.next;
    }
    int[] result = new int[values.size()];
    Stack
<integer> stack = new Stack<>();
    for (int i = 0; i < values.size(); i++) {
        while (!stack.isEmpty() && values.get(i) > values.get(stack.peek())) {
            result[stack.pop()] = values.get(i);
        }
        stack.push(i);
    }
    return result;
}</integer></integer>

🧠 How Devs Usually Mess This Up

Let’s be honest, most of us at 2am have tried one of these classics (don’t lie):

• Poking at pointers: Trying to compare node objects directly? Welcome to null-pointer-exception land.
• Indexing drama: Output is 1-based, not 0-based. Still off by one? The bug is permanent now.
• Looking backwards: Only the next, strictly greater node after counts. The ‘also-rans’ and backwards glances get you zip.
• Brutal double loops: Sure, O(n²) works—for lists shorter than your morning coffee order. For the rest, prepare for pain.

🔍 What’s Actually Going On

Imagine your linked list as a queue at a really exclusive Java conference. Each attendee wonders, “Will someone with a fancier badge line up after me?” Instead of making everyone constantly look over their shoulder (brute force), snap a photo (array conversion), walk the line once, and leave a stack to remember the proud, unchallenged attendees. When a new VIP arrives, anyone previously in the stack with a less impressive badge instantly concedes: “That’s my answer.” Done. No drama, just efficient star-spotting.

🛠️ PseudoCode

• Turn your linked list into an array:

  while (head != null) {
      values.add(head.val);
      head = head.next;
  }

  Linked list to array—the digital version of having eyes in the back of your head.

• Prepare to deliver answers:

  int[] result = new int[values.size()];
  Stack
  <integer> stack = new Stack<>();</integer>

  Result holds the next greater node, stack keeps indices waiting for their upgrade.

• Stack your way through the party:

  for (int i = 0; i < values.size(); i++) {
      while (!stack.isEmpty() && values.get(i) > values.get(stack.peek())) {
          result[stack.pop()] = values.get(i);
      }
      stack.push(i);
  }

  If you see someone with higher value, answer for everyone previously on stack. Moves fast. Looks smart.

• Didn’t find anyone fancier?

  Zero for you. Maybe next time.

💻 The Code

// ListNode class for clarity:
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
 public int[] nextLargerNodes(ListNode head) {
    List
<integer> values = new ArrayList<>();
    while (head != null) {
        values.add(head.val);
        head = head.next;
    }
    int[] result = new int[values.size()];
    Stack
<integer> stack = new Stack<>();
    for (int i = 0; i < values.size(); i++) {
        while (!stack.isEmpty() && values.get(i) > values.get(stack.peek())) {
            result[stack.pop()] = values.get(i);
        }
        stack.push(i);
    }
    return result;
}</integer></integer>

⚠️ Pitfalls, Traps & Runtime Smacks

• Zero means no love. If there’s no greater node, result is zero. Accept it.
• Ties go nowhere: “Next greater” means strictly greater. Tied? Nice try.
• Empty list? Just as empty as your job satisfaction after brute-force. Return an empty array.
• Don’t mess up your indices. Output matches node order. If in doubt, print your array and check it twice.
• Space and time: O(n) both. If you use O(n²) and try to blame Java, Chandler will find you.

🧠 Interviewer Brain-Tattoo

“Don’t reinvent the double loop. Stacks don’t judge—they just work.”