Listas vinculadas idénticas

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *