Programa en C para comprobar si dos listas enlazadas son 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, debemos recorrer ambas listas simultáneamente y, mientras las recorremos, debemos comparar los datos.

// 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 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);
  
    areIdentical(a, b)? printf("Identical"):
                        printf("Not identical");
    return 0;
}

Producción: 

Identical

Método 2 (recursivo): 
el código de solución recursivo es mucho más limpio que el código iterativo. Sin embargo, probablemente no desee utilizar la versión recursiva para el código de producción, ya que utilizará el espacio de pila que es proporcional a la longitud de las listas.

// 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;
}

Complejidad de tiempo: O(n) para versiones iterativas y recursivas. n es la longitud de la lista más pequeña entre a y b.

Consulte el artículo completo sobre listas vinculadas idénticas para obtener más detalles.