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

Normal
0

false
false
false

EN-IN
X-NONE
X-NONE

/* Style Definitions */
table.MsoNormalTable
{mso-style-name:”Table Normal”;
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-priority:99;
mso-style-qformat:yes;
mso-style-parent:””;
mso-padding-alt:0cm 5.4pt 0cm 5.4pt;
mso-para-margin-top:0cm;
mso-para-margin-right:0cm;
mso-para-margin-bottom:8.0pt;
mso-para-margin-left:0cm;
line-height:107%;
mso-pagination:widow-orphan;
font-size:11.0pt;
font-family:”Calibri”,”sans-serif”;
mso-ascii-font-family:Calibri;
mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:”Times New Roman”;
mso-fareast-theme-font:minor-fareast;
mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;}

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.

Algorithm working

C++ Program

 

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

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


void insertAtBeginning(struct LL**head,int dataToBeInserted)
{
	struct LL* curr=new LL;
		
		curr->data=dataToBeInserted;
		curr->next=NULL;
	
	if(*head==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
			*head=curr;
		}
		
		//O(1) constant time
}

bool isIdentical(struct LL **head1 , struct LL **head2)
{
	struct LL *temp1 = *head1 , *temp2 = *head2;
	
	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;
	
}

void display(struct LL**head)
{
	struct LL*temp=*head;
	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
	insertAtBeginning(&head1,6);
	insertAtBeginning(&head1,16);
	insertAtBeginning(&head1,15);
	insertAtBeginning(&head1,50);
	insertAtBeginning(&head1,1);
	insertAtBeginning(&head1,23);
	
	cout <<"First list is :-\n";
	display(&head1);
	
	struct LL *head2 = NULL;
	insertAtBeginning(&head2,6);
	insertAtBeginning(&head2,16);
	insertAtBeginning(&head2,25); //value changed from 15 to 25
	insertAtBeginning(&head2,50);
	insertAtBeginning(&head2,1);
	insertAtBeginning(&head2,23);
	
	cout <<"\nSecond list is :-\n";
	display(&head2);
	
	if(isIdentical(&head1,&head2))
		cout<<"\nGiven lists are identical\n";
	
	else
		cout<<"\nGiven lists are unidentical\n";
	
	return 0;
}

 

Translate »