Given a circular singly linked list, the task is to print the next greater element for each node in the linked list. If there is no next greater element for any node, then print “-1” for that node.
Examples:
Input: head = 1 ? 5 ? 2 ? 10 ? 0 ? (head)
Output: 5 10 10 -1 -1
Explanation:
The next greater elements of each node are:
- Node 1: Next greater element is 5.
- Node 5: Next greater element is 10.
- Node 2: Next greater element is 10.
- Node 10: No next greater element exists. Therefore print “-1”.
- Node 0: No next greater element exists. Therefore print “-1”.
Input: head = 1 ? 5 ? 12 ? 10 ? 0 ? (head)
Output: 5 12 -1 12 -1
Approach: The given problem can be solved by iterating the circular linked list to the right until the same element appears again and then printing the next greater element found for each node. Follow the steps below to solve the problem:
- Initialize a Node variable, say res as NULL to store the head node of the Linked List representing the next greater element.
- Also, initialize a Node variable, say tempList as NULL to iterate over the Linked List representing the next greater element.
- Iterate over the circular Linked List and perform the following steps:
- Initialize a Node, say curr to store the reference to the current node of the circular linked list.
- Initialize a variable say Val as -1 to store the value of the next greater element of the current node.
- Perform the following steps until curr is not equal to the reference of the current node of the circular Linked List:
- If the value at the current node curr is greater than the value of the current node of the circular Linked list then assign the value of curr.data to Val and break out of the loop.
- Update the value of curr node as curr = curr.next.
- If the node res is NULL then create a new node with the value Val and assign it to res, and then assign the value of res to tempList.
- Otherwise, create a new node with the value Val and assign it to tempList.next, and then update the node tempList as tempList = tempList.next.
- After completing the above steps, print the elements of the Linked List res as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h>using namespace std;// Node structure of the circular// Linked liststruct Node { int data; Node *next; // Constructor Node(int d) { data = d; next = NULL; }};// Function to print the elements// of a Linked listvoid print(Node *head){ Node *temp = head; // Iterate the linked list while (temp != NULL) { // Print the data cout << temp->data << " "; temp = temp->next; }}// Function to find the next// greater element for each nodevoid NextGreaterElement(Node *head){ // Stores the head of circular // Linked list Node *H = head; // Stores the head of the // resulting linked list Node *res = NULL; // Stores the temporary head of // the resulting Linked list Node *tempList = NULL; // Iterate until head // is not equal to H do { // Used to iterate over the // circular Linked List Node *curr = head; // Stores if there exist // any next Greater element int Val = -1; // Iterate until head is // not equal to curr do { // If the current node // is smaller if (head->data < curr->data) { // Update the value // of Val Val = curr->data; break; } // Update curr curr = curr->next; } while (curr != head); // If res is Null if (res == NULL) { // Create new Node with // value curr->data res = new Node(Val); // Assign address of // res to tempList tempList = res; } else { // Update tempList tempList->next = new Node(Val); // Assign address of the // next node to tempList tempList = tempList->next; } // Update the value of // head node head = head->next; } while (head != H); // Print the resulting // Linked list print(res);}// Driver codeint main(){ Node *head = new Node(1); head->next = new Node(5); head->next->next = new Node(12); head->next->next->next = new Node(10); head->next->next->next->next = new Node(0); head->next->next->next->next->next = head; NextGreaterElement(head); return 0;}// This code is contributed by mohit kumar 29 |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { static Node head; // Node structure of the circular // Linked list static class Node { int data; Node next; // Constructor public Node(int data) { this.data = data; this.next = null; } } // Function to print the elements // of a Linked list static void print(Node head) { Node temp = head; // Iterate the linked list while (temp != null) { // Print the data System.out.print( temp.data + " "); temp = temp.next; } } // Function to find the next // greater element for each node static void NextGreaterElement(Node head) { // Stores the head of circular // Linked list Node H = head; // Stores the head of the // resulting linked list Node res = null; // Stores the temporary head of // the resulting Linked list Node tempList = null; // Iterate until head // is not equal to H do { // Used to iterate over the // circular Linked List Node curr = head; // Stores if there exist // any next Greater element int Val = -1; // Iterate until head is // not equal to curr do { // If the current node // is smaller if (head.data < curr.data) { // Update the value // of Val Val = curr.data; break; } // Update curr curr = curr.next; } while (curr != head); // If res is Null if (res == null) { // Create new Node with // value curr.data res = new Node(Val); // Assign address of // res to tempList tempList = res; } else { // Update tempList tempList.next = new Node(Val); // Assign address of the // next node to tempList tempList = tempList.next; } // Update the value of // head node head = head.next; } while (head != H); // Print the resulting // Linked list print(res); } // Driver Code public static void main(String[] args) { head = new Node(1); head.next = new Node(5); head.next.next = new Node(12); head.next.next.next = new Node(10); head.next.next.next.next = new Node(0); head.next.next.next.next.next = head; NextGreaterElement(head); }} |
Python3
# Python program for the above approach# Node structure of the circular # Linked listclass Node:# Constructor def __init__(self, data): self.data = data self.next = None # Function to print the elements # of a Linked listdef Print(head): temp = head # Iterate the linked list while (temp != None): # Print the data print(temp.data,end=" ") temp = temp.next# Function to find the next # greater element for each nodedef NextGreaterElement(head): # Stores the head of circular # Linked list H = head # Stores the head of the # resulting linked list res = None # Stores the temporary head of # the resulting Linked list tempList = None # Iterate until head # is not equal to H while(True): # Used to iterate over the # circular Linked List curr = head # Stores if there exist # any next Greater element Val = -1 # Iterate until head is # not equal to curr # If the current node # is smaller while(True): if (head.data < curr.data): # Update the value # of Val Val = curr.data break # Update curr curr = curr.next if(curr == head): break # If res is Null if (res == None): # Create new Node with # value curr.data res = Node(Val) # Assign address of # res to tempList tempList = res else: # Update tempList tempList.next = Node(Val) # Assign address of the # next node to tempList tempList = tempList.next # Update the value of # head node head = head.next if(head == H): break # Print the resulting # Linked list Print(res)# Driver Codehead = Node(1)head.next = Node(5)head.next.next = Node(12)head.next.next.next = Node(10)head.next.next.next.next = Node(0)head.next.next.next.next.next = headNextGreaterElement(head)# This code is contributed by shinjanpatra |
C#
// C# program for the above approachusing System;// Node structure of the circular// Linked listclass Node { public int data; public Node next; // Constructor public Node(int data) { this.data = data; this.next = null; }}class GFG{ static Node head;// Function to print the elements// of a Linked liststatic void print(Node head){ Node temp = head; // Iterate the linked list while (temp != null) { // Print the data Console.Write(temp.data + " "); temp = temp.next; }}// Function to find the next// greater element for each nodestatic void NextGreaterElement(Node head){ // Stores the head of circular // Linked list Node H = head; // Stores the head of the // resulting linked list Node res = null; // Stores the temporary head of // the resulting Linked list Node tempList = null; // Iterate until head // is not equal to H do{ // Used to iterate over the // circular Linked List Node curr = head; // Stores if there exist // any next Greater element int Val = -1; // Iterate until head is // not equal to curr do{ // If the current node // is smaller if (head.data < curr.data) { // Update the value // of Val Val = curr.data; break; } // Update curr curr = curr.next; } while (curr != head); // If res is Null if (res == null) { // Create new Node with // value curr.data res = new Node(Val); // Assign address of // res to tempList tempList = res; } else { // Update tempList tempList.next = new Node(Val); // Assign address of the // next node to tempList tempList = tempList.next; } // Update the value of // head node head = head.next; } while (head != H); // Print the resulting // Linked list print(res);}// Driver Codestatic public void Main(){ head = new Node(1); head.next = new Node(5); head.next.next = new Node(12); head.next.next.next = new Node(10); head.next.next.next.next = new Node(0); head.next.next.next.next.next = head; NextGreaterElement(head);}}// This code is contributed by unknown2108 |
Javascript
<script>// Javascript program for the above approachlet head;// Node structure of the circular // Linked listclass Node{// Constructor constructor(data) { this.data = data; this.next = null; }}// Function to print the elements // of a Linked listfunction print(head){ let temp = head; // Iterate the linked list while (temp != null) { // Print the data document.write( temp.data + " "); temp = temp.next; }}// Function to find the next // greater element for each nodefunction NextGreaterElement(head){ // Stores the head of circular // Linked list let H = head; // Stores the head of the // resulting linked list let res = null; // Stores the temporary head of // the resulting Linked list let tempList = null; // Iterate until head // is not equal to H do { // Used to iterate over the // circular Linked List let curr = head; // Stores if there exist // any next Greater element let Val = -1; // Iterate until head is // not equal to curr do { // If the current node // is smaller if (head.data < curr.data) { // Update the value // of Val Val = curr.data; break; } // Update curr curr = curr.next; } while (curr != head); // If res is Null if (res == null) { // Create new Node with // value curr.data res = new Node(Val); // Assign address of // res to tempList tempList = res; } else { // Update tempList tempList.next = new Node(Val); // Assign address of the // next node to tempList tempList = tempList.next; } // Update the value of // head node head = head.next; } while (head != H); // Print the resulting // Linked list print(res);}// Driver Codehead = new Node(1);head.next = new Node(5);head.next.next = new Node(12);head.next.next.next = new Node(10);head.next.next.next.next = new Node(0);head.next.next.next.next.next = head;NextGreaterElement(head);// This code is contributed by unknown2108</script> |
Output
5 12 -1 12 1
Time Complexity: O(N2)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
