Identical Linked Lists

Identical Linked Lists

In this problem, we have given two linked lists, and we need to check whether the given linked lists are identical or not. Identical means they have the same data, and the arrangement of data is also the same.

Example:

                             List1:2 -> 4 -> 6 -> 8 -> 10

                             List1:2 -> 4 -> 6 -> 8 -> 10

 Output:Identical

Method 1:(Iterative)

In this method, we will traverse both the given linked lists simultaneously, and while traversing, we will compare the data and arrangement of both the linked lists.

Algorithm:

 boolareIdentical(struct node *a, struct node *b)
 {
 while (a != NULL && b != NULL)
     {
 if (a -> info != b -> info)
 return false;
         a = a -> next;
         b = b -> next;
     }
 return (a == NULL && b == NULL);
 } 

An iterative C program to check if two linked lists are identical or not

 #include<stdio.h>
 #include<stdlib.h>
 #include<stdbool.h>
 struct node
 {
 int info;
 struct node * next;
 };
 struct node * start1 = NULL, * start2 = NULL;
 // For inserting the elements in the linked list
 void add(int item, struct node **temp)
 {
 struct node * t, * p;
 t = (struct node * )malloc( sizeof( struct node ));
 if(*temp == NULL)
 {
 * temp = t;
 (* temp) ->info = item;
 (* temp) ->next = NULL;
 return;
 }
 else
 {
 struct node * p = * temp;
 while(p -> next != NULL)
 {
 p = p -> next;
 }
 p -> next = t;
 p = p -> next;
 p -> info = item;
 p -> next = NULL;
 }
 }
 // For checking if two linked lists are identical or not
 boolareIdentical(struct node *a, struct node *b)
 {
 while (a != NULL && b != NULL)
     {
 if (a -> info != b -> info)
 return false;
         a = a -> next;
         b = b -> next;
     }
 return (a == NULL && b == NULL);
 }
 // To display the elements of the linked list
 void traverse(struct node * t)
 {
 if(t == NULL)
 {
             printf(" Linked list is empty\n");
 }
 while(t -> next != NULL)
 {
                         printf("%d -> ", t -> info);
                         t = t -> next;
 }
                         printf("%d\n", t -> info);
 }
 // Driver Function
 int main()
 {
 // Add element into the linked1
 add(1, &start1);
 add(10, &start1);
 add(3, &start1);
 add(4, &start1);
 add(9, &start1);
 add(8, &start1);
 // Add element into the linked2
 add(1, &start2);
 add(10, &start2);
 add(3, &start2);
 add(4, &start2);
 add(9, &start2);
 add(8, &start2);
 printf("list1: ");
 traverse(start1);
 printf("list2: ");
 traverse(start2);
 bool res = areIdentical(start1, start2);
 if(res == 1)
 printf("Linked lists are Identical");
 else
 printf("Linked lists are not Identical");
 return 0;
 } 

Output:

Method 2:(Recursive)

This method will work on a recursive solution to this problem because recursive code is much clearer than iterative code. Recursive code will use the stack space, which is proportional to the length of the linked lists.

Algorithm:

 boolareIdentical(struct Node *a, struct Node *b)
 {
     // If both lists are empty
 if (a == NULL && b == NULL)
 return true;
 if (a != NULL && b != NULL)
 return (a-> info == b -> info) &&
 areIdentical(a->next, b->next);
 return false;
 } 

An recursive C program to check if two linked lists are identical or not

 #include<stdio.h>
 #include<stdlib.h>
 #include<stdbool.h>
 struct node
 {
 int info;
 struct node * next;
 };
 struct node * start1 = NULL, * start2 = NULL;
 // For inserting the elements in the linked list
 void add(int item, struct node **temp)
 {
 struct node * t, * p;
 t = (struct node * )malloc( sizeof( struct node ));
 if(*temp == NULL)
 {
 * temp = t;
 (* temp) ->info = item;
 (* temp) ->next = NULL;
 return;
 }
 else
 {
 struct node * p = * temp;
 while(p -> next != NULL)
 {
 p = p -> next;
 }
 p -> next = t;
 p = p -> next;
 p -> info = item;
 p -> next = NULL;
 }
 }
 // For checking if two linked lists are identical or not
 boolareIdentical(struct node *a, struct node *b)
 {
     // If both linked lists are empty
 if (a == NULL && b == NULL)
 return true;
 if (a != NULL && b != NULL)
 return (a -> info == b -> info) &&
 areIdentical(a -> next, b -> next);
 return false;
 }
 // To display the elements of the linked list
 void traverse(struct node * t)
 {
 if(t == NULL)
 {
             printf(" Linked list is empty\n");
 }
 while(t -> next != NULL)
 {
                         printf("%d -> ", t -> info);
                         t = t -> next;
 }
                         printf("%d\n", t -> info);
 }
 // Driver Function
 int main()
 {
 // Add element into the linked1
 add(1, &start1);
 add(10, &start1);
 add(3, &start1);
 add(4, &start1);
 add(9, &start1);
 add(8, &start1);
 // Add element into the linked2
 add(1, &start2);
 add(10, &start2);
 add(3, &start2);
 add(4, &start2);
 add(9, &start2);
 add(7, &start2);
 printf("list1: ");
 traverse(start1);
 printf("list2: ");
 traverse(start2);
 bool res = areIdentical(start1, start2);
 if(res == 1)
 printf("Linked lists are Identical");
 else
 printf("Linked lists are not Identical");
 return 0;
 } 

Output: