Sublist Search (Search a linked list in another list)

Sublist search is used to discover the presence of one list in another list. Suppose we have a single-node list (let's say the first list), and we want to guarantee that the list is present in another list (let's say the second list), then we can execute the sublist search to discover it. For instance, the first list has these elements: 23 -> 30 -> 41, whereas the second list contains these elements: 10 -> 15 -> 23 -> 30 -> 41 -> 49. At a glance, we note that the first list is presented in the second list.

The sublist search algorithm works by comparing the first element of the first list with the first element of the second list. If the two values don't match, it moves to the next member in the second list. It does this until the two values match.

Given two linked lists, the job is to verify 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:

• Take the first node of the second list.
• Start matching the first list from this first node.
• If whole lists match return true.
• Else break and take the first list to the first node again.
• And take the second list to its second node.
• Repeat these steps until any of the linked lists becomes empty.
• If the first list becomes empty then the list is 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

Time Complexity: O(m*n) where m is the number of nodes in the second list and n in the first.

Optimization

The above code may be optimized by utilizing more space i.e. saves the list into two strings and applying.

Please post comments if you find something inaccurate, or you want to provide additional information about the issue addressed above.