Iterative Approach

Create a boolean function checkIdenticalLists() which takes two parameters one is the head of the first linked list, and the other is the head of another linked list, and store the heads of both the linked lists in two pointers, for example, Node *curr1 = head1, *curr2 = head2;
 Now, traverse both the linked list simultaneously and compare the data of nodes of both the linked list at every point, and if at any moment the data of a specific node of the linked lists are not the same, then return false from the function else continue.
 After completing the loop, we have to check if the length of the linked lists is the same or not and to do so. We have to check if the value of both the pointers is the same.
 After that return true from the function checkIdenticalLists().
Code in C++
// C++ Program to check Identical Linked Lists
#include <bits/stdc++.h>
using namespace std;
// Linked list node
struct Node
{
int val;
Node(int x)
{
val = x;
next = NULL;
}
struct Node *next;
};
// Function to check Identical Linked lists
bool checkIdenticalLists(Node *head1, Node *head2)
{
// curr1 stores the head of the first linked list, and curr2 stores the head of the second linked list
Node *curr1 = head1, *curr2 = head2;
// traversing both the linked list simultaneously
while (curr1 != NULL && curr2 != NULL)
{
if (curr1>val != curr2>val) // if at any point the value of nodes of both the linked list is not same then return false
{
return false;
}
curr1 = curr1>next;
curr2 = curr2>next;
}
if (curr1 != curr2) // checking if both the linked list have same length if not then also returning false
{
return false;
}
// else the linked lists are identical return true
return true;
}
// Function to insert a node
Node *insert(Node *x, int y)
{
Node *temp = new Node(y);
temp>next = x;
return temp;
}
// Driver code
int main()
{
Node *head1 = NULL;
Node *head2 = NULL;
head1 = insert(head1, 10);
head1 = insert(head1, 5);
head1 = insert(head1, 4);
head1 = insert(head1, 11);
head1 = insert(head1, 9);
head2 = insert(head2, 10);
head2 = insert(head2, 5);
head2 = insert(head2, 4);
head2 = insert(head2, 11);
head2 = insert(head2, 9);
if (checkIdenticalLists(head1, head2))
{
cout << "Both linked lists are identical" << endl;
}
else
{
cout << "Both linked lists are not identical" <<endl;
}
return 0;
}
Input:
List1: 10>5>4>11>9
List2: 10>5>4>11>9
Output:
Both linked lists are identical
Complexity Analysis
Time Complexity: O(n) (Worst Case)
Since there are n nodes in the linked list and we are doing traversals of the whole linked list, therefore, the time complexity is O(n)
Space Complexity: O(1) (Worst case)
Since we are not using any data structures other than the linked list given to us, therefore, the space complexity is O(1)
Recursive Approach
 Create a boolean function checkIdenticalLists(), which takes two parameters; one is the head of the first linked list, and the other is the head of another linked list.

Add base case condition to check if the current node of the linked list is NULL or not.
 Compare the current values of the nodes of the linked list and simultaneously make a recursive call for the function; after the call is complete, .it will return true if both the conditions are true, else it will return false.
 To tackle the case where the different lengths of the linked lists are given, add one extra statement of return false outside the if condition stated in the previous step.
Code in C++
// C++ Program to check Identical Linked Lists
#include <bits/stdc++.h>
using namespace std;
// Linked list node
struct Node
{
int val;
Node(int x)
{
val = x;
next = NULL;
}
struct Node *next;
};
// Function to check Identical Linked lists
bool checkIdenticalLists(Node *head1, Node *head2)
{
// we reach the end of both the linked lists, therefore, return true
if (head1 == NULL && head2 == NULL)
{
return true;
}
//checking for the primary condition
if (head1 != NULL && head2 != NULL)
{
// check the value of the current node and also check it recursively for every other node in the linked lists
return (head1>val == head2>val) && checkIdenticalLists(head1>next, head2>next);
}
// One of the lists is empty; therefore, return false
return false;
}
// Function to insert a node
Node *insert(Node *x, int y)
{
Node *temp = new Node(y);
temp>next = x;
return temp;
}
// Driver code
int main()
{
Node *head1 = NULL;
Node *head2 = NULL;
head1 = insert(head1, 1);
head1 = insert(head1, 5);
head1 = insert(head1, 0);
head1 = insert(head1, 7);
head1 = insert(head1, 3);
head2 = insert(head2, 1);
head2 = insert(head2, 5);
head2 = insert(head2, 0);
head2 = insert(head2, 3);
if (checkIdenticalLists(head1, head2))
{
cout << "Both linked list are identical" << endl;
}
else
{
cout << "Both linked lists are not identical" <<endl;
}
return 0;
}
Input:
List1: 1>5>0>7>3
List2: 1>5>0>3
Output:
Both linked lists are not identical.
Complexity Analysis
Time Complexity: O(n) (Worst Case)
Since there are n nodes in the linked list and we are doing traversals of the whole linked list, therefore, the time complexity is O(n)
Space Complexity: O(N) (Worst case)
Since we are making recursive calls there some stack is used it approximately equal to O(n)
Frequently Asked Questions
What is a doublylinked list?
It is a linked list containing pointers to both the previous and next node and has the node's value.
What are the disadvantages of linked lists?
 Memory usage in a linked list is more than an array.
 Reverse traversals are not possible in the linked list.
 Random access is not possible in a linked list.
What are the applications of linked lists?
 They are used in the Implementation of stacks and queues.
 Linked lists are also used to implement graphs, i.e., Adjacency list representation of the graph.
 Arithmetic operations on large integers are done using a linked list.
Conclusion
In this article, we discussed how we could check if two linked lists are identical or not. We discussed two linked approaches; one was using iterative traversal and the other was using recursive traversal.
We hope you gained some insight into this problem, and now it is your turn to practice this problem and code it out in your way.
Don't Stop here. Try more problems in the linked list and gain expertise!
 Check If Linked List Is Palindrome
 Sort Linked List
 Implement Stack With Linked List
 Reverse Linked List
 Segregate Even And Odd Nodes In a Linked List
Recommended Reading:
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
Cheers!