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

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.

Previous post Given a Linked List move the last element to the front
Next post Segregate even and odd nodes in a Linked List

Leave a Reply

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