Dos listas enlazadas son idénticas cuando tienen los mismos datos y la disposición de los datos también es la misma. Por ejemplo, las listas enlazadas a (1->2->3) yb(1->2->3) son idénticas. . Escribe una función para verificar si las dos listas enlazadas dadas son idénticas.
Método 1 (iterativo)
Para identificar si dos listas son idénticas, necesitamos recorrer ambas listas simultáneamente y, mientras las recorremos, debemos comparar datos.
C++
// An iterative C++ program to check if
// two linked lists are identical or not
#include<bits/stdc++.h>
using namespace std;
/* Structure for a linked list node */
struct Node
{
int data;
struct Node *next;
};
/* Returns true if linked lists a and b
are identical, otherwise false */
bool areIdentical(struct Node *a,
struct Node *b)
{
while (a != NULL && b != NULL)
{
if (a->data != b->data)
return false;
/* If we reach here, then a and b are
not NULL and their data is same, so
move to next nodes in both lists */
a = a->next;
b = b->next;
}
// If linked lists are identical, then
// 'a' and 'b' must be NULL at this point.
return (a == NULL && b == NULL);
}
/* UTILITY FUNCTIONS TO TEST fun1() and fun2() */
/* Given a reference (pointer to pointer) to the
head of a list and an int, push a new node on the
front of the list. */
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
// Driver Code
int main()
{
/* The constructed linked lists are :
a: 3->2->1
b: 3->2->1 */
struct Node *a = NULL;
struct Node *b = NULL;
push(&a, 1);
push(&a, 2);
push(&a, 3);
push(&b, 1);
push(&b, 2);
push(&b, 3);
if(areIdentical(a, b))
cout << "Identical";
else
cout << "Not identical";
return 0;
}
// This code is contributed
// by Akanksha Rai
C
// An iterative C program to check if two linked lists are
// identical or not
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
/* Structure for a linked list node */
struct Node
{
int data;
struct Node *next;
};
/* Returns true if linked lists a and b are identical,
otherwise false */
bool areIdentical(struct Node *a, struct Node *b)
{
while (a != NULL && b != NULL)
{
if (a->data != b->data)
return false;
/* If we reach here, then a and b are not NULL and
their data is same, so move to next nodes in both
lists */
a = a->next;
b = b->next;
}
// If linked lists are identical, then 'a' and 'b' must
// be NULL at this point.
return (a == NULL && b == NULL);
}
/* UTILITY FUNCTIONS TO TEST fun1() and fun2() */
/* Given a reference (pointer to pointer) to the head
of a list and an int, push a new node on the front
of the list. */
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Driver program to test above function */
int main()
{
/* The constructed linked lists are :
a: 3->2->1
b: 3->2->1 */
struct Node *a = NULL;
struct Node *b = NULL;
push(&a, 1);
push(&a, 2);
push(&a, 3);
push(&b, 1);
push(&b, 2);
push(&b, 3);
areIdentical(a, b)? printf("Identical"):
printf("Not identical");
return 0;
}
Java
// An iterative Java program to check if two linked lists
// are identical or not
class LinkedList
{
Node head; // head of list
/* Linked list Node*/
class Node
{
int data;
Node next;
Node(int d) { data = d; next = null; }
}
/* Returns true if linked lists a and b are identical,
otherwise false */
boolean areIdentical(LinkedList listb)
{
Node a = this.head, b = listb.head;
while (a != null && b != null)
{
if (a.data != b.data)
return false;
/* If we reach here, then a and b are not null
and their data is same, so move to next nodes
in both lists */
a = a.next;
b = b.next;
}
// If linked lists are identical, then 'a' and 'b' must
// be null at this point.
return (a == null && b == null);
}
/* UTILITY FUNCTIONS TO TEST fun1() and fun2() */
/* Given a reference (pointer to pointer) to the head
of a list and an int, push a new node on the front
of the list. */
void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/* Driver program to test above functions */
public static void main(String args[])
{
LinkedList llist1 = new LinkedList();
LinkedList llist2 = new LinkedList();
/* The constructed linked lists are :
llist1: 3->2->1
llist2: 3->2->1 */
llist1.push(1);
llist1.push(2);
llist1.push(3);
llist2.push(1);
llist2.push(2);
llist2.push(3);
if (llist1.areIdentical(llist2) == true)
System.out.println("Identical ");
else
System.out.println("Not identical ");
}
} /* This code is contributed by Rajat Mishra */
Python3
# An iterative Java program to check if
# two linked lists are identical or not
# Linked list Node
class Node:
def __init__(self, d):
self.data = d
self.next = None
class LinkedList:
def __init__(self):
self.head = None # head of list
# Returns true if linked lists a and b
# are identical, otherwise false
def areIdentical(self, listb):
a = self.head
b = listb.head
while (a != None and b != None):
if (a.data != b.data):
return False
# If we reach here, then a and b
# are not null and their data is
# same, so move to next nodes
# in both lists
a = a.next
b = b.next
# If linked lists are identical,
# then 'a' and 'b' must be null
# at this point.
return (a == None and b == None)
# UTILITY FUNCTIONS TO TEST fun1() and fun2()
# Given a reference (pointer to pointer) to the
# head of a list and an int, push a new node on
# the front of the list.
def push(self, new_data):
# 1 & 2: Allocate the Node &
# Put in the data
new_node = Node(new_data)
# 3. Make next of new Node as head
new_node.next = self.head
# 4. Move the head to point to new Node
self.head = new_node
# Driver Code
llist1 = LinkedList()
llist2 = LinkedList()
# The constructed linked lists are :
# llist1: 3->2->1
# llist2: 3->2->1
llist1.push(1)
llist1.push(2)
llist1.push(3)
llist2.push(1)
llist2.push(2)
llist2.push(3)
if (llist1.areIdentical(llist2) == True):
print("Identical ")
else:
print("Not identical ")
# This code is contributed by Prerna Saini
C#
// An iterative C# program to
// check if two linked lists
// are identical or not
using System;
public class LinkedList
{
Node head; // head of list
/* Linked list Node*/
public class Node
{
public int data;
public Node next;
public Node(int d)
{
data = d; next = null;
}
}
/* Returns true if linked lists
a and b are identical,
otherwise false */
bool areIdentical(LinkedList listb)
{
Node a = this.head, b = listb.head;
while (a != null && b != null)
{
if (a.data != b.data)
return false;
/* If we reach here, then a and b are not null
and their data is same, so move to next nodes
in both lists */
a = a.next;
b = b.next;
}
// If linked lists are identical,
// then 'a' and 'b' must
// be null at this point.
return (a == null && b == null);
}
/* UTILITY FUNCTIONS TO TEST fun1() and fun2() */
/* Given a reference (pointer to pointer) to the head
of a list and an int, push a new node on the front
of the list. */
void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/* Driver code */
public static void Main(String []args)
{
LinkedList llist1 = new LinkedList();
LinkedList llist2 = new LinkedList();
/* The constructed linked lists are :
llist1: 3->2->1
llist2: 3->2->1 */
llist1.push(1);
llist1.push(2);
llist1.push(3);
llist2.push(1);
llist2.push(2);
llist2.push(3);
if (llist1.areIdentical(llist2) == true)
Console.WriteLine("Identical ");
else
Console.WriteLine("Not identical ");
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// An iterative javascript program to check if two linked lists
// are identical or not
class LinkedList{
constructor() {
this.head = null; // head of list
}
}
/* Linked list Node */
class Node {
constructor(d) {
this.data = d;
this.next = null;
}
}
/*
* Returns true if linked lists a and b are identical, otherwise false
*/
function areIdentical( a,b) {
while (a != null && b != null) {
if (a.data != b.data)
return false;
/*
* If we reach here, then a and b are not null and their data is same, so move
* to next nodes in both lists
*/
a = a.next;
b = b.next;
}
// If linked lists are identical, then 'a' and 'b' must
// be null at this point.
return (a == null && b == null);
}
/* UTILITY FUNCTIONS TO TEST fun1() and fun2() */
/*
* Given a reference (pointer to pointer) to the head of a list and an int, push
* a new node on the front of the list.
*/
function push(root,new_data) {
/*
* 1 & 2: Allocate the Node & Put in the data
*/
var new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = root;
/* 4. Move the head to point to new Node */
root = new_node;
return root;
}
/* Driver program to test above functions */
var llist1 = new LinkedList();
var llist2 = new LinkedList();
/*
* The constructed linked lists are : llist1: 3->2->1 llist2: 3->2->1
*/
llist1 = push(llist1,1);
llist1 = push(llist1,2);
llist1 = push(llist1,3);
llist2 = push(llist2,1);
llist2 = push(llist2,2);
llist2 = push(llist2,3);
if (areIdentical(llist1,llist2) == true)
document.write("Identical ");
else
document.write("Not identical ");
// This code is contributed by Rajput-Ji
</script>
C++
// A recursive C++ function to check if two linked
// lists are identical or not
bool areIdentical(Node *a, Node *b)
{
// If both lists are empty
if (a == NULL && b == NULL)
return true;
// If both lists are not empty, then data of
// current nodes must match, and same should
// be recursively true for rest of the nodes.
if (a != NULL && b != NULL)
return (a->data == b->data) &&
areIdentical(a->next, b->next);
// If we reach here, then one of the lists
// is empty and other is not
return false;
}
//This is code is contributed by rathbhupendra
C
// A recursive C function to check if two linked
// lists are identical or not
bool areIdentical(struct Node *a, struct Node *b)
{
// If both lists are empty
if (a == NULL && b == NULL)
return true;
// If both lists are not empty, then data of
// current nodes must match, and same should
// be recursively true for rest of the nodes.
if (a != NULL && b != NULL)
return (a->data == b->data) &&
areIdentical(a->next, b->next);
// If we reach here, then one of the lists
// is empty and other is not
return false;
}
Java
// A recursive Java method to check if two linked
// lists are identical or not
boolean areIdenticalRecur(Node a, Node b)
{
// If both lists are empty
if (a == null && b == null)
return true;
// If both lists are not empty, then data of
// current nodes must match, and same should
// be recursively true for rest of the nodes.
if (a != null && b != null)
return (a.data == b.data) &&
areIdenticalRecur(a.next, b.next);
// If we reach here, then one of the lists
// is empty and other is not
return false;
}
/* Returns true if linked lists a and b are identical,
otherwise false */
boolean areIdentical(LinkedList listb)
{
return areIdenticalRecur(this.head, listb.head);
}
Python3
# A recursive Python3 function to check # if two linked lists are identical or not def areIdentical(a, b): # If both lists are empty if (a == None and b == None): return True # If both lists are not empty, # then data of current nodes must match, # and same should be recursively true # for rest of the nodes. if (a != None and b != None): return ((a.data == b.data) and areIdentical(a.next, b.next)) # If we reach here, then one of the lists # is empty and other is not return False # This code is contributed by Princi Singh
C#
// A recursive C# method to
// check if two linked lists
// are identical or not
bool areIdenticalRecur(Node a, Node b)
{
// If both lists are empty
if (a == null && b == null)
return true;
// If both lists are not empty, then data of
// current nodes must match, and same should
// be recursively true for rest of the nodes.
if (a != null && b != null)
return (a.data == b.data) &&
areIdenticalRecur(a.next, b.next);
// If we reach here, then one of the lists
// is empty and other is not
return false;
}
/* Returns true if linked lists
a and b are identical, otherwise false */
bool areIdentical(LinkedList listb)
{
return areIdenticalRecur(this.head, listb.head);
}
}
// This code is contributed by princiraj1992
Javascript
<script>
// A recursive javascript method to check if two linked
// lists are identical or not
function areIdenticalRecur( a, b)
{
// If both lists are empty
if (a == null && b == null)
return true;
// If both lists are not empty, then data of
// current nodes must match, and same should
// be recursively true for rest of the nodes.
if (a != null && b != null)
return (a.data == b.data) &&
areIdenticalRecur(a.next, b.next);
// If we reach here, then one of the lists
// is empty and other is not
return false;
}
/* Returns true if linked lists a and b are identical,
otherwise false */
function areIdentical( listb)
{
return areIdenticalRecur(this.head, listb.head);
}
// This code contributed by aashish1995
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA