Next Greater Node In Linked List - CPP Solution

1. Introduction

In this blog post, we will tackle a problem involving a linked list where the goal is to find the next greater node for each node in the list. This is a common problem in data structure manipulation, emphasizing the use of stack data structures to efficiently process each node.

Problem

Given the head of a linked list with n nodes, the task is to find the value of the next greater node for each node. Specifically, for each node, we need to find the value of the first node that is next to it and has a strictly larger value. We need to return an array of integers where each element represents the value of the next greater node for each node in the list. If a node does not have a next greater node, the corresponding value in the array should be set to 0.

2. Solution Steps

1. Traverse the linked list and store each node's value in a vector.

2. Use a stack to keep track of the indices of the nodes while traversing the vector.

3. For each element in the vector, while the stack is not empty and the current element is greater than the element at the index at the top of the stack, update the answer for that index.

4. Push the current index onto the stack.

5. Return the answer vector.

3. Code Program

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

// ListNode structure definition
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Function to find the next greater node for each node in the list
vector<int> nextLargerNodes(ListNode* head) {
    vector<int> values, result;
    for (ListNode* node = head; node != nullptr; node = node->next) {
        values.push_back(node->val);
    }

    stack<int> s;
    result.resize(values.size(), 0);
    for (int i = 0; i < values.size(); ++i) {
        while (!s.empty() && values[i] > values[s.top()]) {
            result[s.top()] = values[i];
            s.pop();
        }
        s.push(i);
    }

    return result;
}

// Function to print the result
void printResult(const vector<int>& result) {
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    // Creating a linked list: 2 -> 7 -> 4 -> 3 -> 5
    ListNode* head = new ListNode(2);
    head->next = new ListNode(7);
    head->next->next = new ListNode(4);
    head->next->next->next = new ListNode(3);
    head->next->next->next->next = new ListNode(5);

    vector<int> result = nextLargerNodes(head);
    printResult(result); // Expected output: 7 0 5 5 0
    return 0;
}

Output:

7 0 5 5 0

Explanation:

The nextLargerNodes function first converts the linked list into a vector of values. It then iterates through this vector, using a stack to keep track of indices. For each element, it checks if the current element is greater than the element at the top of the stack. If so, it updates the result for that index with the current element's value. 

This approach efficiently computes the next greater node for each node in the list using a stack to keep track of the candidates for the next greater node.