Next Greater Node In Linked List

Next Greater Node In Linked List

What is this problem about?

The Next Greater Node In Linked List problem gives you a singly linked list of integers. For each node, find the value of the next node in the list that is strictly greater, and return these values as an array. Nodes with no greater successor get value 0. This coding problem combines linked list traversal with monotonic stack processing.

Why is this asked in interviews?

Microsoft, Amazon, Google, and Bloomberg ask this to test whether candidates can apply the monotonic stack pattern to a linked list — a data structure where indexing isn't directly available. The linked list, array, monotonic stack, and stack interview pattern is central, and converting the linked list to an array first is the cleanest approach.

Algorithmic pattern used

Convert to array + monotonic decreasing stack. First, traverse the linked list and store all values in an array. Initialize a result array of the same size with zeros. Process the values array with a decreasing monotonic stack (storing indices). For each element, pop all stack entries with smaller values and record the current value as their next-greater answer. This gives O(n) time overall.

Example explanation

Linked list: 2→7→4→3→5. Array: [2,7,4,3,5]. Result: [0,0,0,0,0].

• i=0 (2): push index 0.
• i=1 (7): 7>arr[0]=2 → result[0]=7, pop. Push 1. Stack: [1].
• i=2 (4): 4<7, push. Stack: [1,2].
• i=3 (3): 3<4, push. Stack: [1,2,3].
• i=4 (5): 5>arr[3]=3 → result[3]=5, pop. 5>arr[2]=4 → result[2]=5, pop. 5<arr[1]=7 → stop. Push 4. Result: [7, 0, 5, 5, 0].

Common mistakes candidates make

• Trying to use a two-pointer approach on the linked list directly (O(n²)).
• Not initializing the result array with zeros before processing.
• Storing values instead of indices in the stack (need indices to update result array).
• Off-by-one in result array size vs linked list length.

Interview preparation tip

When a standard array algorithm (like monotonic stack) is applied to a linked list, always convert the list to an array first — this simplifies indexing and avoids pointer manipulation errors. The time complexity remains O(n). Practice this "convert then apply" pattern for linked list problems that are naturally array-based. It demonstrates pragmatic thinking that interviewers appreciate over elegant but buggy pointer-based solutions.