Lecture 154:- Next Greater Element In LL

Finding the next greater element in a linked list can be done using a stack. For each element in the linked list, you need to find the next element that is greater than the current element. Here's how you can approach this problem:

1. Traverse the linked list from left to right.
2. For each element, push it onto the stack.
3. While the stack is not empty and the current element is greater than the top element of the stack, pop elements from the stack and update their next greater elements.
4. Push the current element onto the stack.
5. After the traversal, the elements remaining in the stack do not have a next greater element.

Here's a C++ implementation of finding the next greater element in a linked list:

cppCopy code

#include <iostream> #include <stack> class Node { public: int data; Node* next; Node(int value) : data(value), next(nullptr) {} }; void nextGreaterElement(Node* head) { if (!head) return; std::stack<Node*> nodeStack; while (head) { while (!nodeStack.empty() && head->data > nodeStack.top()->data) { nodeStack.top()->data = head->data; nodeStack.pop(); } nodeStack.push(head); head = head->next; } while (!nodeStack.empty()) { nodeStack.top()->data = -1; // No greater element found nodeStack.pop(); } } void displayList(Node* head) { while (head) { std::cout << head->data << " "; head = head->next; } std::cout << std::endl; } int main() { Node* head = new Node(4); head->next = new Node(5); head->next->next = new Node(2); head->next->next->next = new Node(10); std::cout << "Original List: "; displayList(head); nextGreaterElement(head); std::cout << "List with Next Greater Elements: "; displayList(head); return 0; }

In this example, the nextGreaterElement function calculates the next greater elements for each node in the linked list using a stack. The displayList function is used to display the original and modified lists.

For the input list [4, 5, 2, 10], the output will be [5, 10, 10, -1], which represents the next greater elements for each node.

.