Given two linked lists, the task is to check whether the first list is present in 2nd list or not.
Input : list1 = 10->20
list2 = 5->10->20
Output : LIST FOUND
Input : list1 = 1->2->3->4
list2 = 1->2->1->2->3->4
Output : LIST FOUND
Input : list1 = 1->2->3->4
list2 = 1->2->2->1->2->3
Output : LIST NOT FOUND
Algorithm:
1- Take first node of second list.
2- Start matching the first list from this first node.
3- If whole lists match return true.
4- Else break and take first list to the first node again.
5- And take second list to its second node.
6- Repeat these steps until any of linked lists becomes empty.
7- If first list becomes empty then list found else not.
Below is C++ implementation.
// C++ program to find a list in second list #include <bits/stdc++.h> using namespace std; // A Linked List node struct Node { int data; Node* next; }; // Returns true if first list is present in second // list bool findList(Node* first, Node* second) { Node* ptr1 = first, *ptr2 = second; // If both linked lists are empty, return true if (first == NULL && second == NULL) return true; // Else If one is empty and other is not return // false if ( first == NULL || (first != NULL && second == NULL)) return false; // Traverse the second list by picking nodes // one by one while (second != NULL) { // Initialize ptr2 with current node of second ptr2 = second; // Start matching first list with second list while (ptr1 != NULL) { // If second list becomes empty and first // not then return false if (ptr2 == NULL) return false; // If data part is same, go to next // of both lists else if (ptr1->data == ptr2->data) { ptr1 = ptr1->next; ptr2 = ptr2->next; } // If not equal then break the loop else break; } // Return true if first list gets traversed // completely that means it is matched. if (ptr1 == NULL) return true; // Initialize ptr1 with first again ptr1 = first; // And go to next node of second list second = second->next; } return false; } /* Function to print nodes in a given linked list */void printList(Node* node) { while (node != NULL) { printf("%d ", node->data); node = node->next; } } // Function to add new node to linked lists Node *newNode(int key) { Node *temp = new Node; temp-> data= key; temp->next = NULL; return temp; } /* Driver program to test above functions*/int main() { /* Let us create two linked lists to test the above functions. Created lists shall be a: 1->2->3->4 b: 1->2->1->2->3->4*/ Node *a = newNode(1); a->next = newNode(2); a->next->next = newNode(3); a->next->next->next = newNode(4); Node *b = newNode(1); b->next = newNode(2); b->next->next = newNode(1); b->next->next->next = newNode(2); b->next->next->next->next = newNode(3); b->next->next->next->next->next = newNode(4); findList(a,b) ? cout << "LIST FOUND" : cout << "LIST NOT FOUND"; return 0; } |
Output:
LIST FOUND
Time Complexity : O(m*n) where m is the number of nodes in second list and n in first.
Optimization :
Above code can be optimized by using extra space i.e. stores the list into two strings and apply .
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments