# Check if two linked lists are identical

## Find whether the given two linked lists are identical or not

To check whether two linked lists are identical or not. Both the linked lists should have same data and they should be in same order to be identical.

### Example

In the above diagram
a, b → Not identical
a, c → Not identical
a, d → Identical
b, c → Not identical
b, d → Not identical

## Algorithm

Time Complexity : O(n)
O(n) n is length of smaller list.
Space Complexity : O(n)

Step 1 : We create a function to check identical.
Step 2 : We compare the elements of Linked lists till last element which are at same position.
a)    If both heads are NULL return true.
b)    Compare each element data and move the pointers forward in both linked lists till it reaches the end.
c)    If any list remains untraversed means the lists are not identical. So, return false
d)    Else they are identical. So, return true.

Step 4 : Create two linked lists and call the function on them. If true prints identical, else prints not identical.

## C++ Program

``````#include <bits/stdc++.h>
using namespace std;

struct LL{
int data;
LL *next;
};

{
struct LL* curr=new LL;

curr->data=dataToBeInserted;
curr->next=NULL;

*head=curr; //if this is first node make this as head of list

else
{
curr->next=*head; //else make the current (new) node's next point to head and make this new node a the head
}

//O(1) constant time
}

{

while(temp1 != NULL and temp2 != NULL) //till any of the list ends
{
if(temp1->data != temp2->data)	//match each element's data
return false;

//move both the pointers forward
temp1 = temp1->next;
temp2 = temp2->next;
}

//if any list remains untraversed means the lists are not identical
if(temp1 || temp2)
return false;

return true;

}

{
while(temp!=NULL)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;

temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}

int main()
{

struct LL *head1 = NULL; //initial list has no elements

cout <<"First list is :-\n";

insertAtBeginning(&head2,25); //value changed from 15 to 25

cout <<"\nSecond list is :-\n";