### 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

#includeusing 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.