Next Greater Node In Linked List - Practice Coding Problems

Next Greater Node In Linked List - Problem

You are given the head of a linked list with n nodes.

For each node in the list, find the value of the next greater node. That is, for each node, find the value of the first node that is next to it and has a strictly larger value than it.

Return an integer array answer where answer[i] is the value of the next greater node of the i-th node (1-indexed). If the i-th node does not have a next greater node, set answer[i] = 0.

Input & Output

Example 1 — Basic Case

$ Input: head = [2,1,5]

› Output: [5,5,0]

💡 Note: For node 2: next greater is 5. For node 1: next greater is 5. For node 5: no next greater, so 0.

Example 2 — Increasing Sequence

$ Input: head = [1,7,5,1,9,2,5,1]

› Output: [7,9,9,9,0,5,0,0]

💡 Note: Each node finds its next greater element: 1→7, 7→9, 5→9, 1→9, 9→none, 2→5, 5→none, 1→none.

Example 3 — Decreasing Sequence

$ Input: head = [5,4,3,2,1]

› Output: [0,0,0,0,0]

💡 Note: No node has a next greater element since the sequence is strictly decreasing.

Constraints

The number of nodes in the list is in the range [1, 10⁴]
1 ≤ Node.val ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Linked list [2,1,5] - find next greater for each

Process

For each node, look ahead to find first greater value

Output

Array [5,5,0] - next greater values or 0 if none

Key Takeaway

🎯 Key Insight: Use a monotonic stack to efficiently track elements waiting for their next greater element in O(n) time

Asked in

a Amazon 45 M Microsoft 32 G Google 28

The key insight is using a monotonic stack to efficiently track elements waiting for their next greater element. The optimal approach converts the linked list to an array, then uses a stack to store indices of elements in decreasing order. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Monotonic Stack - One Pass	O(n)	O(n)	Use stack to track elements waiting for their next greater element
Brute Force - Nested Traversal	O(n²)	O(n)	For each node, traverse remaining list to find next greater

Monotonic Stack - One Pass — Algorithm Steps

Convert linked list to array
Use stack to store indices of elements waiting for next greater
For each element, resolve waiting elements and add current to stack

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Elements

For each element, resolve waiting smaller elements

Stack Operations

Pop smaller elements (found answer), push current

Final Result

All elements processed with O(n) time

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

int* solution(struct ListNode* head, int* returnSize) {
    // Convert linked list to array
    int values[1000];
    int n = 0;
    struct ListNode* current = head;
    while (current) {
        values[n++] = current->val;
        current = current->next;
    }
    
    int* result = (int*)calloc(n, sizeof(int));
    int stack[1000]; // Store indices
    int stackSize = 0;
    *returnSize = n;
    
    for (int i = 0; i < n; i++) {
        // Pop elements that found their next greater
        while (stackSize > 0 && values[stack[stackSize-1]] < values[i]) {
            int idx = stack[--stackSize];
            result[idx] = values[i];
        }
        
        // Push current index
        stack[stackSize++] = i;
    }
    
    return result;
}

struct ListNode* buildLinkedList(int* arr, int size) {
    if (size == 0) return NULL;
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->val = arr[0];
    head->next = NULL;
    struct ListNode* current = head;
    for (int i = 1; i < size; i++) {
        current->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        current->next->val = arr[i];
        current->next->next = NULL;
        current = current->next;
    }
    return head;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int headArray[1000];
    int size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int num = atoi(token);
        if (num != 0 || token[0] == '0') {
            headArray[size++] = num;
        }
        token = strtok(NULL, "[,]");
    }
    
    struct ListNode* head = buildLinkedList(headArray, size);
    int returnSize;
    int* result = solution(head, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each element is pushed and popped from stack at most once

✓ Linear Growth

Space Complexity

O(n)

Stack can hold up to n elements in worst case (decreasing sequence)

⚡ Linearithmic Space

152.0K Views

Medium Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Monotonic Stack - One Pass — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler