Dada una lista circular enlazada individualmente , la tarea es imprimir el siguiente elemento mayor para cada Node en la lista enlazada . Si no hay un siguiente elemento mayor para ningún Node, imprima «-1» para ese Node.
Ejemplos:
Entrada: cabeza = 1 → 5 → 2 → 10 → 0 → (cabeza)
Salida: 5 10 10 -1 -1
Explicación:
Los siguientes elementos mayores de cada Node son:
- Node 1: El siguiente elemento mayor es 5.
- Node 5: El siguiente elemento mayor es 10.
- Node 2: El siguiente elemento mayor es 10.
- Node 10: No existe el siguiente elemento mayor. Por lo tanto imprima «-1».
- Node 0: No existe el siguiente elemento mayor. Por lo tanto imprima «-1».
Entrada: cabeza = 1 → 5 → 12 → 10 → 0 → (cabeza)
Salida: 5 12 -1 12 -1
Enfoque: el problema dado se puede resolver iterando la lista circular enlazada hacia la derecha hasta que el mismo elemento aparezca nuevamente y luego imprimiendo el siguiente elemento mayor encontrado para cada Node. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable de Node, diga res como NULL para almacenar el Node principal de la lista enlazada que representa el siguiente elemento mayor.
- Además, inicialice una variable de Node, diga tempList como NULL para iterar sobre la lista enlazada que representa el siguiente elemento mayor.
- Iterar sobre la lista enlazada circular y realizar los siguientes pasos:
- Inicialice un Node, diga curr para almacenar la referencia al Node actual de la lista enlazada circular.
- Inicialice una variable, digamos Val como -1 para almacenar el valor del siguiente elemento mayor del Node actual .
- Realice los siguientes pasos hasta que curr no sea igual a la referencia del Node actual de la Lista Enlazada circular:
- Si el valor en el Node actual curr es mayor que el valor del Node actual de la lista enlazada circular, entonces asigne el valor de curr.data a Val y salga del ciclo .
- Actualice el valor del Node curr como curr = curr.next .
- Si el Node res es NULL , cree un nuevo Node con el valor Val y asígnelo a res , y luego asigne el valor de res a tempList .
- De lo contrario, cree un nuevo Node con el valor Val y asígnelo a tempList.next y luego actualice el Node tempList como tempList = tempList.next.
- Después de completar los pasos anteriores, imprima los elementos de la lista enlazada como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Node structure of the circular
// Linked list
struct Node
{
int data;
Node *next;
// Constructor
Node(int d)
{
data = d;
next = NULL;
}
};
// Function to print the elements
// of a Linked list
void 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 node
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
int 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 approach
import 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 list class Node: # Constructor def __init__(self, data): self.data = data self.next = None # Function to print the elements # of a Linked list def 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 node def 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 Code head = 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 = head NextGreaterElement(head) # This code is contributed by shinjanpatra
C#
// C# program for the above approach
using System;
// Node structure of the circular
// Linked list
class 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 list
static 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 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
static 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 approach
let head;
// Node structure of the circular
// Linked list
class Node
{
// Constructor
constructor(data)
{
this.data = data;
this.next = null;
}
}
// Function to print the elements
// of a Linked list
function 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 node
function 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 Code
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
</script>
Producción
5 12 -1 12 1
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por zack_aayush y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA