Site icon Study Algorithms

Write a code to check if 2 linked lists are identical.

Question: Write a program to check if 2 linked lists are identical?

Method 1(Iterative):-

To Determine if both Linked lists are identical, we need to traverse both lists simultaneously, and while traversing we need to compare data of each node.

Implementation

//returns 1 if both lists are identical or returns 0
int areIdenticalLinkedList(struct node * list1, struct node * list2)
{
	while(1)
	{
		// return 1 if both are NULL
		if(list1 == NULL && list2 == NULL)
			return 1;
		
		// return 0 if one of them is NULL
		if(list1 == NULL || list2 == NULL)
			return 0;

		if(list1 -> data != list2 -> data)
			return 0;
			
		list1 = list1 -> next;
		list2 = list2 -> next;
	}
}

Method2( Recursive):-

//returns 1 if both lists are identical or returns 0
int areIdenticalLinkedListRecursive(struct node * list1, struct node * list2)
{
	// return 1 if both are same
	if (list1 == NULL && list2 == NULL)
		return 1;

	// return 0 if one of them is different
	if (list1 == NULL || list2 == NULL)
		return 0;

	if (list1 -> data != list2 -> data)
		return 0;

	// the recursive call
	return areIdenticalLinkedListRecursive(list1 -> next, list2 -> next);
}

It may seem that both recursive and iterative implementation are the same but the iterative version is recommended since it offers better control and the recursive implementation maintains a stack of all the callbacks.

Exit mobile version