Replace every node of a Linked list with the next greater element on right side
Given a linked list, the task is to find the Next Greater Element for every node of the linked list.
Note: For nodes with no next greater element, store -1 in the result.
Examples:
Input: linked list = [2, 1, 5]
Output: [5, 5, -1]Input: linked list = [2, 7, 4, 3, 5]
Output: [7, -1, 5, 5, -1]
Approach:
To solve the problem mentioned above the main idea is to use a Stack Data Structure.
- Iterate through the linked list and insert the value and position of elements of the linked list into a stack.
- Initialize the result vector with -1 for every node.
- Update the previous node’s value while the current node’s value is greater than the previous nodes and pop the value from the stack after updating.
Below is the implementation of the above approach:
C++
// C++ Program to find the // Next Greater Element for // a Linked List #include <bits/stdc++.h> using namespace std; // Linked List Node struct Node { int val; struct Node* next; }; // Function to print // next greater element vector< int > nextLargerNodes( struct Node* head) { int cur_pos = 0; stack<pair< int , int > > arr; vector< int > res; // Iterate for all // element in linked list while (head) { // Initialize every // position with 0 res.push_back(-1); // Check if current value is // greater then update previous while ( !arr.empty() && arr.top().second < head->val) { res[arr.top().first] = head->val; arr.pop(); } arr.push(make_pair( cur_pos, head->val)); cur_pos++; // Increment the head pointer head = head->next; } // Return the final result return res; } // Utility function to // create a new node Node* newNode( int val) { struct Node* temp = new Node; temp->val = val; temp->next = NULL; return temp; } // Driver Program int main() { struct Node* head = newNode(2); head->next = newNode(7); head->next->next = newNode(4); head->next->next->next = newNode(3); head->next->next->next->next = newNode(5); vector< int > ans; ans = nextLargerNodes(head); for ( int i = 0; i < ans.size(); i++) { cout << ans[i] << ", " ; } } |
Java
// Java Program to find the // Next Greater Element for // a Linked List import java.util.*; class GFG{ // Linked List Node static class Node { int val; Node next; }; static class pair { int first, second; public pair( int first, int second) { this .first = first; this .second = second; } } ; // Function to print // next greater element static Vector<Integer> nextLargerNodes(Node head) { int cur_pos = 0 ; Stack<pair > arr = new Stack<>(); Vector<Integer> res = new Vector<>(); // Iterate for all // element in linked list while (head != null ) { // Initialize every // position with 0 res.add(- 1 ); // Check if current value is // greater then update previous while (!arr.isEmpty() && arr.peek().second < head.val) { res.set(arr.peek().first, head.val); arr.pop(); } arr.add( new pair(cur_pos, head.val)); cur_pos++; // Increment the head // pointer head = head.next; } // Return the final result return res; } // Utility function to // create a new node static Node newNode( int val) { Node temp = new Node(); temp.val = val; temp.next = null ; return temp; } // Driver code public static void main(String[] args) { Node head = newNode( 2 ); head.next = newNode( 7 ); head.next.next = newNode( 4 ); head.next.next.next = newNode( 3 ); head.next.next.next.next = newNode( 5 ); Vector<Integer> ans = new Vector<>(); ans = nextLargerNodes(head); for ( int i = 0 ; i < ans.size(); i++) { System.out.print(ans.elementAt(i) + ", " ); } } } // This code is contributed by Princi Singh |
Python3
# Python3 program to find the # Next Greater Element for # a Linked List # Linked List Node class newNode: def __init__( self , val): self .val = val self . next = None # Function to print # next greater element def nextLargerNodes(head): cur_pos = 0 arr = [] res = [] # Iterate for all # element in linked list while (head): # Initialize every # position with 0 res.append( - 1 ) # Check if current value is # greater then update previous while ( len (arr) > 0 and arr[ len (arr) - 1 ][ 1 ] < head.val): res[arr[ len (arr) - 1 ][ 0 ]] = head.val arr.remove(arr[ len (arr) - 1 ]) arr.append([cur_pos, head.val]) cur_pos + = 1 # Increment the head pointer head = head. next # Return the final result return res # Driver code if __name__ = = '__main__' : head = newNode( 2 ) head. next = newNode( 7 ) head. next . next = newNode( 4 ) head. next . next . next = newNode( 3 ) head. next . next . next . next = newNode( 5 ) ans = nextLargerNodes(head) for i in range ( len (ans)): print (ans[i], end = ", " ) # This code is contributed by SURENDRA_GANGWAR |
C#
// C# Program to find the // Next Greater Element for // a Linked List using System; using System.Collections.Generic; class GFG{ // Linked List Node class Node { public int val; public Node next; }; class pair { public int first, second; public pair( int first, int second) { this .first = first; this .second = second; } } ; // Function to print // next greater element static List< int > nextLargerNodes(Node head) { int cur_pos = 0; Stack<pair > arr = new Stack<pair>(); List< int > res = new List< int >(); // Iterate for all // element in linked list while (head != null ) { // Initialize every // position with 0 res.Add(-1); // Check if current value is // greater then update previous while (arr.Count !=0 && arr.Peek().second < head.val) { res[arr.Peek().first] = head.val; arr.Pop(); } arr.Push( new pair(cur_pos, head.val)); cur_pos++; // Increment the head // pointer head = head.next; } // Return the readonly result return res; } // Utility function to // create a new node static Node newNode( int val) { Node temp = new Node(); temp.val = val; temp.next = null ; return temp; } // Driver code public static void Main(String[] args) { Node head = newNode(2); head.next = newNode(7); head.next.next = newNode(4); head.next.next.next = newNode(3); head.next.next.next.next = newNode(5); List< int > ans = new List< int >(); ans = nextLargerNodes(head); for ( int i = 0; i < ans.Count; i++) { Console.Write(ans[i] + ", " ); } } } // This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript program to find the // Next Greater Element for // a Linked List // Linked List Node class newNode{ constructor(val){ this .val = val this .next = null } } // Function to print // next greater element function nextLargerNodes(head){ let cur_pos = 0 let arr = [] let res = [] // Iterate for all // element in linked list while (head){ // Initialize every // position with 0 res.push(-1) // Check if current value is // greater then update previous while (arr.length> 0 && arr[arr.length- 1][1] < head.val){ res[arr[arr.length- 1][0]] = head.val arr.pop() } arr.push([cur_pos, head.val]) cur_pos += 1 // Increment the head pointer head = head.next } // Return the final result return res } // Driver code let head = new newNode(2) head.next = new newNode(7) head.next.next = new newNode(4) head.next.next.next = new newNode(3) head.next.next.next.next = new newNode(5) ans = nextLargerNodes(head) for (let i=0;i<ans.length;i++) document.write(ans[i], ", " ) // This code is contributed by shinjanpatra </script> |
Output:
7, -1, 5, 5, -1,
Time Complexity: O(N)
Auxiliary Space Complexity: O(N)