This blog contains the solution of the problem “how to check two linked lists are equal”. Checking identical linked lists is a must to know the problem of the linked list. Knowledge about Linked List always gives you an advantage in coding prospective.
How To Check Two Linked Lists Are Equal
In this problem, we are given two LinkedList and are asked to find if the linked lists are identical or not i.e. we have to find whether the two linked lists have the same arrangement of the values of the nodes in them or not.
Linked list 1:
Linked List 2:
Output: Identical
These two LinkedList are identical.
Let’s first understand the problem statement with the help of an example:
If Linked list 1 = 3→5→7 and Linked list 2 = 3→5→7.
The term ‘arrangement of the values of the nodes in a linked list’ which we have referred to in the problem statement means that if our linked list is 5→6→7→8→9, then the arrangement of the values of the nodes in the linked list is 5,6,7,8,9.
- From the Linked list 1 we can see that its arrangement of the values of the nodes is 3,5,7.
- From the Linked list 2 we can see that its arrangement of the values of the nodes is 3,5,7.
Since both the linked list have the same arrangement of the values of the nodes, so the above linked list 1 and 2 are Identical.
If Linked list 1 = 3→5→6 and Linked list 2 = 3→6→5.
- From the Linked list 1 we can see that its arrangement of the values of the nodes is 3,5,6.
- From the Linked list 2 we can see that its arrangement of the values of the nodes is 3,6,5.
Since both the linked list have a different arrangement of the values of the nodes, so the above linked list 1 and 2 are Not Identical.
Now, I think from the above examples, it is clear what we are trying to find in this problem. So next we will try to think about how we can approach this problem.
Before jumping to the next section of the blog, try to think about how you can solve this problem?
Approach on How To Check Two Linked Lists Are Equal
The basic approach which comes to mind is to traverse both the linked list simultaneously and check if at any iteration:
- The values of the lists are different then we return false.
Else if we reach the end of both the lists at the same time while traversing then only we return true.
Note: If we reach the end in only one list that means their size is different and hence also not identical.
Algorithm on How To Check Two Linked Lists Are Equal
- Start traversing the linked lists x and y.
- If at any point while traversing, the data is different in the two lists (x->data != y->data), then we return false.
- If we reach the end of both the linked list at the same time, then we return true.
- If we reach the end of any one of the lists then they are not identical and return false.
Dry Run on How To Check Two Linked Lists Are Equal
Code Implementation on How To Check Two Linked Lists Are Equal
#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;
}
#include<bits stdc++.h="">
using namespace std;
struct Node
{
int data;
struct Node *next;
};
bool areIdentical(struct Node *x,struct Node *y)
{
while (x != NULL && y != NULL)
{
if (x->data != y->data)
return false;
x = x->next;
y = y->next;
}
return (x == NULL && y == NULL);
}
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
int main()
{
struct Node *x = NULL;
struct Node *y = NULL;
push(&x, 7);
push(&x, 5);
push(&x, 3);
push(&y, 7);
push(&y, 5);
push(&y, 3);
if(areIdentical(x, y))
cout << "Identical";
else
cout << "Not identical";
return 0;
}
class Identical
{
Node head;
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(Identical llist2)
{
Node a = this.head, b = llist2.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);
}
void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
/* Driver program to test above functions */
public static void main(String args[])
{
Identical llist1=new Identical();
Identical llist2=new Identical();
/* 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 ");
}
}
class Node:
def __init__(self, d):
self.data = d
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def areIdentical(self, listb):
a = self.head
b = listb.head
while (a != None and b != None):
if (a.data != b.data):
return False
a = a.next
b = b.next
return (a == None and b == None)
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
llist1 = LinkedList()
llist2 = LinkedList()
llist1.push(7)
llist1.push(5)
llist1.push(3)
llist2.push(7)
llist2.push(5)
llist2.push(3)
if (llist1.areIdentical(llist2) == True):
print("Identical ")
else:
print("Not identical ")
Output
IdenticalTime Complexity of Finding identical linked lists: O(min(m,n)), where m,n are the size of the linked lists.
Space Complexity of Finding identical linked lists: O(1), no extra space is used.
This article has an efficient approach for “How To Check Two Linked Lists Are Equal” with approach, algorithm, dry run and code implementation. This is a basic question and if you want to practice more such questions on linked lists, feel free to solve them at Linked List.
FAQ
1. Can we compare two nodes in the linked list?
You’re given the pointer to the head nodes of two linked lists. Compare the data in the nodes of the linked lists to check if they are equal. If all data attributes are equal and the lists are the same length, return
2. How do you count a linked list?
An iterative approach for finding the length of the linked list:
Initialize count as 0.
Initialize a node pointer, current = head.
Do the following while current is not NULL. current = current -> next. Increment count by 1.
Return count.
3. What is the linked list?
A linked list is a sequence of data structures, which are connected together via links. Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list is the second most-used data structure after array.