Sublist Search (Search a linked list in another list)

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

Input  : list1 =  1->2->3->4
         list2  = 1->2->1->2->3->4

Input  : list1 =  1->2->3->4
         list2  = 1->2->2->1->2->3

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;



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.

This article is attributed to GeeksforGeeks.org

leave a comment



load comments

Subscribe to Our Newsletter