Sublist Search (Search a linked list in another list)

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

Given two linked lists, our task is to check whether the first list is present in the second list or not.

Problem Statement Understanding

Let’s try to understand the problem statement with the help of examples.

According to the problem statement, we will be given two linked lists list1 and list2, and we need to check whether list1 is present in list2 or not.

• If list1 is present in list2, we will output Found.
• Otherwise, we will output Not Found.

If the given linked lists are list1: 1→2→4 and list2: 1→2→1→2→4→3.

• As we can see, in list2 starting from the 3^rd index and up to 5^th index (1→2→4) (considering 1 based indexing), list2 contains all the elements of list 1 in the same order as they are present in list1. So we can say that list2 contains list1.
• We will output Found, as we found our list1 in list2.

Say, if the list1: 1→2→4 and list2: 1→2→1→2→3→4.

• As we can see that list2 does not contain all the elements of list1 in the same order as they were present in list1, so we will output Not Found.

Some more examples

Sample Input 1: list1 = 3→5, list2 =5→3→5.
Sample Output 1: Found

Sample Input 2: list1 = 1→3→4, list2 = 1→2→1→3→5.
Sample Output 2: Not Found

Remember: Here we are doing a sublist search, so if all the elements of list1 are present in list2 in the same order as they were present in list1 and these elements are consecutive in list2, then only we can say that we found list1 in list2.

Now I think from the above examples, the problem statement is clear. So let's see how we will approach it. Any Ideas?

• If not, it's okay. We will see in the next section thoroughly how we can approach this problem.

Let’s move to the next section.

Approach and Algorithm

• Start traversing through both the list.
• Match every node of the 2nd list (list2) with the first node of the 1st list (list1).
• If the first node of the 1st list matches with the current node of the 2nd list.
  • Then, we have to check whether the remaining nodes of 1st List matches the nodes of 2nd list or not.
  • If all nodes of 1st list (list1) are matched with 2nd list (list2), then return true.
• If all nodes of list1 didn’t match with list2 nodes, we will move forward in list2 and repeat the above process from step 2.
• Until any of the list1 or list2 becomes empty, we will repeat the above process.
• If our list1 got empty, then we can say that list1 found in list2, else not.

Dry Run

Code Implementation

#include 
using namespace std;
 
//  Linked List node structure
struct Node
{
    int data;
    Node* next;
};
 
//This searchList function will return true if list1 is present in list2
bool searchList(Node* list1, Node* list2)
{
    Node* p1 = list1, *p2 = list2;
 
    if (list1 == NULL && list2 == NULL)
        return true;
 
    if ( list1 == NULL || (list1 != NULL && list2 == NULL))
        return false;
 
    while (list2 != NULL)
    {
        p2 = list2;
 
        while (p1 != NULL)
        {
            if (p2 == NULL)
                return false;
 
            
            else if (p1->data == p2->data)
            {
                p1 = p1->next;
                p2 = p2->next;
            }
            else break;
        }
 
        if (p1 == NULL)
            return true;
 
        p1 = list1;
 
        list2 = list2->next;
    }
 
    return false;
}
 
/* This function is used to print the nodes of a given linked list */
void printList(Node* node)
{
    while (node != NULL)
    {
        printf("%d ", node->data);
        node = node->next;
    }
}
 
// This function is used to add a new node to a linked list
Node *newNode(int key)
{
    Node *temp = new Node;
    temp-> data= key;
    temp->next = NULL;
    return temp;
}
 
int main()
{
    Node *list1 = newNode(1);
    list1->next = newNode(2);
    list1->next->next = newNode(4);
 
    Node *list2 = newNode(1);
    list2->next = newNode(2);
    list2->next->next = newNode(1);
    list2->next->next->next = newNode(2);
    list2->next->next->next->next = newNode(4);
    list2->next->next->next->next->next = newNode(3);
 
    searchList(list1,list2) ? cout << "Found" :
                    cout << "Not Found";
 
    return 0;
}

Output

Found

Time Complexity: O(M * N), M is the size of lsit1 and N is the size of list2.

So, In this blog, we have learned How to Search a linked list in another list. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.