# Identical linked lists: Find if two lists are equal

```List1: 1->2->3->4->5->NULL
List2: 1->2->3->4->5->NULL
Output: true

List1: 1->2->3->4->NULL
List2: 1->2->3->NULL
Output: false```

Time tested method to check equality of two things is to use hash. In this case, put node values of first list in hash and look for nodes of second list. Also, make sure all elements put into hash are checked at least once.

```1. Put all nodes in list 1 in hash.
2. Scan second list.
2.a If any node in second list is not present in hash, return false.
3. If any element in hash is not checked once, then return false.
4. Return true;```

Complexity is O(n+m) where n and m are length of two list. Also, space complexity will be O(n) to store n values of first linked list.

Second method is to scan both linked list simultaneously and compare nodes. Algorithm will be :

```1. For all nodes in first and second list
1.a If data of nodes is not equal, return false.
2. If both linked list are finished, return true. Else return false```

Complexity of algorithm to determine identical linked lists is O(n) with with O(1) space complexity.

Third way is to use recursion. If current nodes of two lists are equal, problem reduces to check if two sublists are identical. Base case will be to check if both lists are finished or not. Below is recursive implementation to find if two linked list are identical.

### Identical linked lists : Recursive implementation

Complexity of recursive solution too is O(n), however there is an implicit space complexity O(n).