Identical linked lists
Given two singly linked lists, find if two linked lists are identical linked lists. For example:
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. 1.b advance to next nodes in both linked lists. 2. If both linked list are finished, return true. Else return false
Identical linked list implementation
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).
Please share if you find something wrong or suggestions. Sharing is caring. If you are interested in contributing to website or have an interview experience to share, please contact us.