Dadas dos listas enlazadas circulares L1 y L2 , la tarea es encontrar si las dos listas enlazadas circulares son idénticas o no.
Nota: El encabezado de cualquier lista vinculada apunta a cualquier Node de la lista vinculada respectiva y las listas pueden contener elementos duplicados.
Ejemplos :
Entrada : L1: 1 -> 2 -> 3 -> 4 -> 5 -> 1 -> 2 -> 6
L2: 5 -> 1 -> 2 -> 6 -> 1 -> 2 -> 3 -> 4
Salida : Sí.
Explicación: si se marcó el quinto elemento de L1 y el primer elemento de L2, entonces son idénticos.
Como son circulares, no importa desde dónde empecemos a comprobar.Entrada : L1: 1 -> 2 -> 3
L2: 1 ->3 -> 2
Salida : No
Enfoque : el problema se puede resolver recorriendo la lista circular enlazada utilizando la siguiente idea:
Fijar el punto de partida de cualquier lista. Ahora considere cada elemento de la otra lista como cabeza y compare si ambas listas son idénticas o no para ese punto de partida.
Siga los pasos que se mencionan a continuación para resolver el problema:
- Calcule la longitud l1 y l2 de ambas listas circulares enlazadas respectivamente
- Si ambas longitudes son diferentes, devuelve falso
- Inicializar recuento = 0 , indicador = falso
- Inicializar punteros temporales, h1 y h2 para head1 (puntero de inicio de l1) y head2 (puntero de inicio de l2)
- Traverse mientras no devuelve un bool, verdadero o falso:
- Si los datos de h1 son iguales a los datos de h2, cambie h1 y h2 a su siguiente Node y aumente la cuenta en 1.
- Si Count es igual a l1 (o l2 ), las listas vinculadas son idénticas, devuelve verdadero
- De lo contrario, restablezca el puntero h1 y el conteo de variables a su estado inicial.
- Si, indicador == 1, devuelve falso , ya que significa que se completó una rotación, y ahora, si el elemento no coincide, la lista no puede ser idéntica.
- Si, h2->next = head2 entonces se completa una rotación, luego se establece, flag = 1
- Mueva el puntero h2 1 posición, h2 = h2->next .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to Check that two circular
// linked list are identical or not
#include <bits/stdc++.h>
using namespace std;
// Circular Linked list Node Class
class Node {
public:
int data;
Node* next;
// Constructor function
Node(int data)
{
this->data = data;
this->next = NULL;
}
};
// Function to insert a node in
// tail in circular linked list
void insertNode(Node*& head,
Node*& tail, int d)
{
// First insertion in circular
// linked list
if (head == NULL) {
Node* newNode = new Node(d);
head = newNode;
tail = newNode;
newNode->next = newNode;
}
else {
// Non-empty list
Node* temp = new Node(d);
temp->next = tail->next;
tail->next = temp;
tail = tail->next;
}
}
// Function to print circular linked list
void print(Node* head)
{
Node* curr = head;
// If circular linked list is empty
if (head == NULL) {
cout << "List is Empty " << endl;
return;
}
// Else iterate until node is NOT head
do {
cout << curr->data << " ";
curr = curr->next;
} while (curr != head);
cout << endl;
}
// Function to return length of
// circular linked list
int length(Node* head)
{
// If circular linked list is empty
if (head == NULL) {
return 0;
}
int size = 0;
Node* curr = head;
// Else iterate until node is NOT head
do {
curr = curr->next;
size++;
} while (curr != head);
return size;
}
// Function to Check that two circular
// linked list are identical or not
bool checkIdentical(Node*& head1,
Node*& head2)
{
// Get the length of first linked list
int l1 = length(head1);
// Get the length of first linked list
int l2 = length(head2);
// If l1!=l2 then linked list can not
// be identical
if (l1 != l2)
return false;
// Initialize the variables
int Count = 0;
bool flag = 0;
// Initialize temporary pointers
Node* h1 = head1;
Node* h2 = head2;
// Traverse the list
while (1) {
// If element matches in two
// circular linked list
if (h1->data == h2->data) {
h1 = h1->next;
Count++;
// If count equals to l1(or l2)
// then linked list are identical
if (Count == l1)
return true;
}
// If element does not matches
// in two circular linked list
else {
h1 = head1;
Count = 0;
// If flag becomes 1 then one
// rotation is complete and
// if now data does not match then
// linked lists are not identical
if (flag)
return false;
}
// Check if h2 complete one rotation
if (h2->next == head2)
flag = 1;
// Move h2 to h2->next
h2 = h2->next;
}
}
// Driver Code
int main()
{
Node* head1 = NULL;
Node* tail1 = NULL;
insertNode(head1, tail1, 1);
insertNode(head1, tail1, 2);
insertNode(head1, tail1, 3);
insertNode(head1, tail1, 4);
insertNode(head1, tail1, 5);
insertNode(head1, tail1, 1);
insertNode(head1, tail1, 2);
insertNode(head1, tail1, 6);
Node* head2 = NULL;
Node* tail2 = NULL;
insertNode(head2, tail2, 5);
insertNode(head2, tail2, 1);
insertNode(head2, tail2, 2);
insertNode(head2, tail2, 6);
insertNode(head2, tail2, 1);
insertNode(head2, tail2, 2);
insertNode(head2, tail2, 3);
insertNode(head2, tail2, 4);
bool flag = checkIdentical(head1, head2);
if (flag)
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java program to Check that two circular
// linked list are identical or not
public class Identical {
// Circular Linked list Node Class
static class Node {
int data;
Node next;
// Constructor function
Node(int data)
{
this.data = data;
this.next = null;
}
};
// Function to insert a node in
// tail in circular linked list
static Node insertNode(Node head, Node tail, int d)
{
// First insertion in circular
// linked list
if (head == null) {
Node newNode = new Node(d);
head = newNode;
tail = newNode;
newNode.next = newNode;
return newNode;
}
else {
// Non-empty list
Node temp = new Node(d);
temp.next = tail.next;
tail.next = temp;
return tail.next;
}
}
// Function to print circular linked list
static void print(Node head)
{
Node curr = head;
// If circular linked list is empty
if (head == null) {
System.out.println("List is Empty ");
return;
}
// Else iterate until node is NOT head
do {
System.out.print(curr.data + " ");
curr = curr.next;
} while (curr != head);
System.out.println();
}
// Function to return length of
// circular linked list
static int length(Node head)
{
// If circular linked list is empty
if (head == null) {
return 0;
}
int size = 0;
Node curr = head;
// Else iterate until node is NOT head
do {
curr = curr.next;
size++;
} while (curr != head);
return size;
}
// Function to Check that two circular
// linked list are identical or not
static boolean checkIdentical(Node head1, Node head2)
{
// Get the length of first linked list
int l1 = length(head1);
// Get the length of first linked list
int l2 = length(head2);
// If l1!=l2 then linked list can not
// be identical
if (l1 != l2)
return false;
// Initialize the variables
int Count = 0;
boolean flag = false;
// Initialize temporary pointers
Node h1 = head1;
Node h2 = head2;
// Traverse the list
while (true) {
// If element matches in two
// circular linked list
if (h1.data == h2.data) {
h1 = h1.next;
Count++;
// If count equals to l1(or l2)
// then linked list are identical
if (Count == l1)
return true;
}
// If element does not matches
// in two circular linked list
else {
h1 = head1;
Count = 0;
// If flag becomes 1 then one
// rotation is complete and
// if now data does not match then
// linked lists are not identical
if (flag)
return false;
}
// Check if h2 complete one rotation
if (h2.next == head2)
flag = true;
// Move h2 to h2.next
h2 = h2.next;
}
}
static Node head1, tail1, head2, tail2;
// Driver Code
public static void main(String[] args)
{
head1 = null;
tail1 = null;
head1 = tail1 = insertNode(head1, tail1, 1);
tail1 = insertNode(head1, tail1, 2);
tail1 = insertNode(head1, tail1, 3);
tail1 = insertNode(head1, tail1, 4);
tail1 = insertNode(head1, tail1, 5);
tail1 = insertNode(head1, tail1, 1);
tail1 = insertNode(head1, tail1, 2);
tail1 = insertNode(head1, tail1, 6);
head2 = null;
tail2 = null;
head2 = tail2 = insertNode(head2, tail2, 5);
tail2 = insertNode(head2, tail2, 1);
tail2 = insertNode(head2, tail2, 2);
tail2 = insertNode(head2, tail2, 6);
tail2 = insertNode(head2, tail2, 1);
tail2 = insertNode(head2, tail2, 2);
tail2 = insertNode(head2, tail2, 3);
tail2 = insertNode(head2, tail2, 4);
boolean flag = checkIdentical(head1, head2);
if (flag)
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Lovely Jain
C#
// C# program to check that two circular linked lists are
// indentical or not.
using System;
class GFG {
// node
class Node {
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
};
/* Function to insert a node
at tail in Circular linked list */
static Node insertNode(Node head, Node tail, int d)
{
// if list is empty
if (head == null) {
Node new_node = new Node(d);
head = new_node;
tail = new_node;
new_node.next = new_node;
return new_node;
}
// if list is non-empty
else {
Node temp = new Node(d);
temp.next = tail.next;
tail.next = temp;
return tail.next;
}
}
// Function to return length of circular linked list.
static int length(Node head)
{
if (head == null) {
return 0;
}
int size = 0;
Node curr = head;
do {
curr = curr.next;
size++;
} while (curr != head);
return size;
}
// Function to check that two circualr linked list are
// identical or not
static bool checkIdentical(Node head1, Node head2)
{
// Get the length of first linked list
int l1 = length(head1);
// Get the length of second linked list
int l2 = length(head2);
// If l1!=l2 then linked list can not
// be identical
if (l1 != l2)
return false;
// Initialize the variables
int count = 0;
bool flag = false;
// Initialize temporary nodes
Node h1 = head1;
Node h2 = head2;
// Traverse the list
while (true) {
// If element matches in two
// circular linked list
if (h1.data == h2.data) {
h1 = h1.next;
count++;
// If count equals to l1(or l2)
// then linked list are identical
if (count == l1) {
return true;
}
}
// If element does not matches
// in two circular linked list
else {
h1 = head1;
count = 0;
// If flag becomes 1 then one
// rotation is complete and
// if now data does not match then
// linked lists are not identical
if (flag) {
return false;
}
}
// Check if h2 complete one rotation
if (h2.next == head2) {
flag = true;
}
// Move h2 to h2.next
h2 = h2.next;
}
}
// Driver Code
static public void Main(String[] args)
{
/* Initialize lists as empty */
Node head1 = null;
Node head2 = null;
Node tail1 = null;
Node tail2 = null;
/* Created linked list will
be 11.2.56.12 */
head1 = tail1 = insertNode(head1, tail1, 1);
tail1 = insertNode(head1, tail1, 2);
tail1 = insertNode(head1, tail1, 3);
tail1 = insertNode(head1, tail1, 4);
tail1 = insertNode(head1, tail1, 5);
tail1 = insertNode(head1, tail1, 1);
tail1 = insertNode(head1, tail1, 2);
tail1 = insertNode(head1, tail1, 6);
head2 = tail2 = insertNode(head2, tail2, 5);
tail2 = insertNode(head2, tail2, 1);
tail2 = insertNode(head2, tail2, 2);
tail2 = insertNode(head2, tail2, 6);
tail2 = insertNode(head2, tail2, 1);
tail2 = insertNode(head2, tail2, 2);
tail2 = insertNode(head2, tail2, 3);
tail2 = insertNode(head2, tail2, 4);
bool flag = checkIdentical(head1, head2);
if (flag)
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by lokesh (lokeshmvs21).
Python3
# Python code for the above approach
# Node Class
class Node:
def __init__(self, d):
self.data = d
self.next = None
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
## Function to insert a node in
## tail in circular linked list
def insertNode(self, d):
## First insertion in circular
## linked list
if (self.head == None):
newNode = Node(d);
self.head = newNode;
self.tail = newNode;
newNode.next = newNode;
else:
## Non-empty list
temp = Node(d);
temp.next = self.tail.next;
self.tail.next = temp;
self.tail = self.tail.next;
## Function to print circular linked list
def printList(self):
curr = self.head
if(self.head == None):
print("List is Empty")
return
## Else iterate until node is NOT head
print(curr.data, " ", end='')
curr = curr.next
while curr != self.head:
print(curr.data, " ", end='')
curr = curr.next
print("\n")
## Function to reverse a node
def length(self):
if (self.head == None):
return 0
size = 0;
curr = self.head;
## Else iterate until node is NOT head
size += 1
curr = curr.next
while (curr != self.head):
curr = curr.next
size += 1
return size
def checkIdentical(self, llist):
## Get the length of first linked list
l1 = self.length()
## Get the length of first linked list
l2 = llist.length()
## If l1!=l2 then linked list can not
## be identical
if (l1 != l2):
return False;
## Initialize the variables
Count = 0;
flag = 0;
## Initialize temporary pointers
h1 = self.head;
h2 = llist.head;
## Traverse the list
while True:
## If element matches in two
## circular linked list
if (h1.data == h2.data):
h1 = h1.next;
Count += 1
## If count equals to l1 or l2
## then linked list are identical
if (Count == l1):
return True
## If element does not matches
## in two circular linked list
else:
h1 = self.head;
Count = 0;
## If flag becomes 1 then one
## rotation is complete and
## if now data does not match then
## linked lists are not identical
if (flag):
return False
## Check if h2 complete one rotation
if (h2.next == llist.head):
flag = 1;
## Move h2 to h2.next
h2 = h2.next
# Driver Code
if __name__=='__main__':
llist1 = LinkedList()
llist2 = LinkedList()
llist1.insertNode(1)
llist1.insertNode(2)
llist1.insertNode(3)
llist1.insertNode(4)
llist1.insertNode(5)
llist1.insertNode(1)
llist1.insertNode(2)
llist1.insertNode(6)
llist2.insertNode(5)
llist2.insertNode(1)
llist2.insertNode(2)
llist2.insertNode(6)
llist2.insertNode(1)
llist2.insertNode(2)
llist2.insertNode(3)
llist2.insertNode(4)
flag = llist1.checkIdentical(llist2)
if flag:
print("Yes")
else:
print("No")
# This code is contributed by subhamgoyal2014.
Javascript
<script>
// JavaScript code for the above approach
// Node Class
class Node{
constructor(d){
this.data = d
this.next = null
}
}
class LinkedList{
constructor(){
this.head = null
this.tail = null
}
// Function to insert a node in
// tail in circular linked list
insertNode(d){
// First insertion in circular
// linked list
if (this.head == null){
let newNode = new Node(d);
this.head = newNode;
this.tail = newNode;
newNode.next = newNode;
}
else{
// Non-empty list
let temp = new Node(d);
temp.next = this.tail.next;
this.tail.next = temp;
this.tail = this.tail.next;
}
}
// Function to print circular linked list
printList(){
let curr = this.head
if(this.head == null){
document.write("List is Empty","</br>")
return
}
// Else iterate until node is NOT head
document.write(curr.data," ")
curr = curr.next
while(curr != this.head){
document.write(curr.data, " ")
curr = curr.next
}
document.write("</br>")
}
// Function to reverse a node
length(){
if (this.head == null)
return 0
let size = 0;
let curr = this.head;
// Else iterate until node is NOT head
size += 1
curr = curr.next
while (curr != this.head){
curr = curr.next
size += 1
}
return size
}
checkIdentical(llist){
// Get the length of first linked list
let l1 = this.length()
// Get the length of first linked list
let l2 = llist.length()
// If l1!=l2 then linked list can not
// be identical
if (l1 != l2)
return false;
// Initialize the variables
let Count = 0;
let flag = 0;
// Initialize temporary pointers
let h1 = this.head;
let h2 = llist.head;
// Traverse the list
while(true){
// If element matches in two
// circular linked list
if (h1.data == h2.data){
h1 = h1.next;
Count += 1
// If count equals to l1 or l2
// then linked list are identical
if (Count == l1)
return true
}
// If element does not matches
// in two circular linked list
else{
h1 = this.head;
Count = 0;
// If flag becomes 1 then one
// rotation is complete and
// if now data does not match then
// linked lists are not identical
if (flag)
return false
}
// Check if h2 complete one rotation
if (h2.next == llist.head)
flag = 1;
// Move h2 to h2.next
h2 = h2.next
}
}
}
// Driver Code
let llist1 = new LinkedList()
let llist2 = new LinkedList()
llist1.insertNode(1)
llist1.insertNode(2)
llist1.insertNode(3)
llist1.insertNode(4)
llist1.insertNode(5)
llist1.insertNode(1)
llist1.insertNode(2)
llist1.insertNode(6)
llist2.insertNode(5)
llist2.insertNode(1)
llist2.insertNode(2)
llist2.insertNode(6)
llist2.insertNode(1)
llist2.insertNode(2)
llist2.insertNode(3)
llist2.insertNode(4)
let flag = llist1.checkIdentical(llist2)
if(flag)
document.write("Yes","</br>")
else
document.write("No","</br>")
// This code is contributed by shinjanpatra
</script>
Producción
Yes
Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por akashjha2671 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA