Identical Linked Lists

Problem Statement

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.

Problem Statement Understanding

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

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

  • 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

Code Implementation


#include
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;
}

#include
#include
#include
 
/* 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;
}
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

Identical

Time Complexity: O(min(m,n)), where m,n are the size of the linked lists.

Space Complexity: O(1), no extra space is used.

This blog tried to discuss if the two linked lists are identical or not using simple traversal. 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.

Leave a Reply

Your email address will not be published. Required fields are marked *