Sublist Search (Search a linked list in another list)

Last Updated : 07 May, 2023

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

Examples:

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

Approach 1:

Take first node of second list.
Start matching the first list from this first node.
If whole lists match return true.
Else break and take first list to the first node again.
And take second list to its second node.
Repeat these steps until any of linked lists becomes empty.
If first list becomes empty then list found else not.

Implementation:

C++

// 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;
}

Java

// Java program to find a list in second list
import java.util.*;
public class GFG 
{ 
 
// A Linked List node
static class Node 
{
    int data;
    Node next;
};
 
// Returns true if first list is 
// present in second list
static boolean 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 */
static void printList(Node node)
{
    while (node != null)
    {
        System.out.printf("%d ", node.data);
        node = node.next;
    }
}
 
// Function to add new node to linked lists
static Node newNode(int key)
{
    Node temp = new Node();
    temp.data= key;
    temp.next = null;
    return temp;
}
 
// Driver Code
public static void main(String[] args) 
{
    /* 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);
 
    if(findList(a, b) == true) 
        System.out.println("LIST FOUND");
    else
        System.out.println("LIST NOT FOUND");
}
}
 
// This code is contributed by Princi Singh

Python3

# Python3 program to find a list in second list 
class Node:
    def __init__(self, value = 0):
         
        self.value = value
        self.next = None
 
# Returns true if first list is 
# present in second list 
def findList(first, second):
     
    # If both linked lists are empty/None,
    # return True
    if not first and not second:
        return True
 
    # If ONLY one of them is empty,
    # return False
    if not first or not second:
        return False
 
    ptr1 = first
    ptr2 = second
 
    # Traverse the second LL by 
    # picking nodes one by one
    while ptr2:
 
        # Initialize 'ptr2' with current
        # node of 'second'
        ptr2 = second
 
        # Start matching first LL 
        # with second LL
        while ptr1:
 
            # If second LL become empty and 
            # first not, return False,
            # since first LL has not been 
            # traversed completely
            if not ptr2:
                return False
 
            # If value of both nodes from both
            # LLs are equal, increment pointers
            # for both LLs so that next value 
            # can be matched
            elif ptr1.value == ptr2.value:
                ptr1 = ptr1.next
                ptr2 = ptr2.next
 
            # If a single mismatch is found
            # OR ptr1 is None/empty,break out
            # of the while loop and do some checks
            else:
                break
 
        # check 1 :
        # If 'ptr1' is None/empty,that means
        # the 'first LL' has been completely
        # traversed and matched so return True
        if not ptr1:
            return True
 
        # If check 1 fails, that means, some 
        # items for 'first' LL are still yet
        # to be matched, so start again by 
        # bringing back the 'ptr1' to point
        # to 1st node of 'first' LL
        ptr1 = first
         
        # And increment second node element to next
        second = second.next
         
    return False
 
# Driver Code
 
# Let us create two linked lists to
# test the above functions.
# Created lists would be
# node_a: 1->2->3->4
# node_b: 1->2->1->2->3->4
node_a = Node(1)
node_a.next = Node(2)
node_a.next.next = Node(3)
node_a.next.next.next = Node(4)
 
node_b = Node(1)
node_b.next = Node(2)
node_b.next.next = Node(1)
node_b.next.next.next = Node(2)
node_b.next.next.next.next = Node(3)
node_b.next.next.next.next.next = Node(4)
 
if findList(node_a, node_b):
    print("LIST FOUND")
else:
    print("LIST NOT FOUND")
 
# This code is contributed by GauriShankarBadola

C#

// C# program to find a list in second list
using System;
 
class GFG 
{ 
 
// A Linked List node
class Node 
{
    public int data;
    public Node next;
};
 
// Returns true if first list is 
// present in second list
static Boolean 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 */
static void printList(Node node)
{
    while (node != null)
    {
        Console.Write("{0} ", node.data);
        node = node.next;
    }
}
 
// Function to add new node to linked lists
static Node newNode(int key)
{
    Node temp = new Node();
    temp.data= key;
    temp.next = null;
    return temp;
}
 
// Driver Code
public static void Main(String[] args) 
{
    /* 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);
 
    if(findList(a, b) == true) 
        Console.Write("LIST FOUND");
    else
        Console.Write("LIST NOT FOUND");
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// JavaScript program to find a 
// list in second list
 
    // A Linked List node
    class Node {
    constructor() {
        this.data = 0;
        this.next = null;
    }
}
 
    // Returns true if first list is
    // present in second list
    function findList(first,  second) {
    var 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 */
    function printList(node) {
        while (node != null) {
            document.write("%d ", node.data);
            node = node.next;
        }
    }
 
    // Function to add new node to linked lists
    function newNode(key) {
        var temp = new Node();
        temp.data = key;
        temp.next = null;
        return temp;
    }
 
    // Driver Code
     
        /*
         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
         */
        var a = newNode(1);
        a.next = newNode(2);
        a.next.next = newNode(3);
        a.next.next.next = newNode(4);
  
        var 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);
 
        if (findList(a, b) == true)
            document.write("LIST FOUND");
        else
            document.write("LIST NOT FOUND");
 
// This code contributed by gauravrajput1
 
</script>

Output

LIST FOUND

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

Optimization:

Above code can be optimized by using extra space i.e. storing the list into two strings and applying KMP algorithm.

Approach 2: Using recursion

Time complexity :- O(n*m)

The time complexity of this implementation is O(n*m), where n is the length of the main list and m is the length of the sublist. This is because in the worst case, we may have to iterate through the entire main list for each node in the sublist.

Space complexity :- O(m)

The space complexity of this implementation is O(m), where m is the length of the sublist. This is because we are only keeping track of one node at a time from the sublist, so the space required is proportional to the length of the sublist.

Define a Node class with an int data member and a Node* pointer to the next node in the linked list.
Define a recursive isSublist function that takes two Node* pointers as parameters: list (the main list) and sublist (the sublist to search for in the main list).
In the isSublist function, handle the base cases:
a. If sublist is nullptr, i.e., the end of the sublist has been reached, return true because the sublist has been found.
b. If list is nullptr, i.e., the end of the main list has been reached but the sublist has not been found, return false.
In the recursive case of the isSublist function:
a. If the data member of the current list node is equal to the data member of the current sublist node, recursively call isSublist with the next nodes in both lists (list->next and sublist->next).
b. If the data member of the current list node is not equal to the data member of the current sublist node, recursively call isSublist with the next node in the main list (list->next) and the entire sublist (sublist).
In the main function:
a. Create a main linked list called list with 6 nodes, each with an int data member.
b. Create a sublist called sublist with 4 nodes, each with an int data member.
c. Call the isSublist function with list and sublist as arguments.
d. If the isSublist function returns true, print “LIST FOUND”. Otherwise, print “LIST NOT FOUND”.
Return 0 to exit the program.

C++

#include <iostream>
 
using namespace std;
 
class Node {
public:
    int data;
    Node* next;
 
    Node(int data)
    {
        this->data = data;
        next = nullptr;
    }
};
 
bool isSublist(Node* list, Node* sublist)
{
    // Base cases
    if (sublist == nullptr) {
        return true;
    }
    if (list == nullptr) {
        return false;
    }
 
    // Recursive case
    if (list->data == sublist->data) {
        return isSublist(list->next, sublist->next);
    }
    else {
        return isSublist(list->next, sublist);
    }
}
 
int main()
{
    // Create the main list
    Node* list = new Node(1);
    list->next = new Node(2);
    list->next->next = new Node(1);
    list->next->next->next = new Node(2);
    list->next->next->next->next = new Node(3);
    list->next->next->next->next->next = new Node(4);
 
    // Create the sublist
    Node* sublist = new Node(1);
    sublist->next = new Node(2);
    sublist->next->next = new Node(3);
    sublist->next->next->next = new Node(4);
 
    // Check if sublist is present in list
    if (isSublist(list, sublist)) {
        cout << "LIST FOUND" << endl;
    }
    else {
        cout << "LIST NOT FOUND" << endl;
    }
 
    return 0;
}

Java

class Node {
    public int data;
    public Node next;
 
    public Node(int data)
    {
        this.data = data;
        next = null;
    }
}
 
public class Main {
    public static boolean isSublist(Node list, Node sublist)
    {
        // Base cases
        if (sublist == null) {
            return true;
        }
        if (list == null) {
            return false;
        }
 
        // Recursive case
        if (list.data == sublist.data) {
            return isSublist(list.next, sublist.next);
        }
        else {
            return isSublist(list.next, sublist);
        }
    }
 
    public static void main(String[] args)
    {
        // Create the main list
        Node list = new Node(1);
        list.next = new Node(2);
        list.next.next = new Node(1);
        list.next.next.next = new Node(2);
        list.next.next.next.next = new Node(3);
        list.next.next.next.next.next = new Node(4);
 
        // Create the sublist
        Node sublist = new Node(1);
        sublist.next = new Node(2);
        sublist.next.next = new Node(3);
        sublist.next.next.next = new Node(4);
 
        // Check if sublist is present in list
        if (isSublist(list, sublist)) {
            System.out.println("LIST FOUND");
        }
        else {
            System.out.println("LIST NOT FOUND");
        }
    }
}

Python3

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
def isSublist(list, sublist):
    # Base cases
    if sublist is None:
        return True
    if list is None:
        return False
 
    # Recursive case
    if list.data == sublist.data:
        return isSublist(list.next, sublist.next)
    else:
        return isSublist(list.next, sublist)
 
# Create the main list
list = Node(1)
list.next = Node(2)
list.next.next = Node(1)
list.next.next.next = Node(2)
list.next.next.next.next = Node(3)
list.next.next.next.next.next = Node(4)
 
# Create the sublist
sublist = Node(1)
sublist.next = Node(2)
sublist.next.next = Node(3)
sublist.next.next.next = Node(4)
 
# Check if sublist is present in list
if isSublist(list, sublist):
    print("LIST FOUND")
else:
    print("LIST NOT FOUND")

C#

using System;
 
class Node {
    public int data;
    public Node next;
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}
 
class Sublist {
    public static bool IsSublist(Node list, Node sublist) {
        // Base cases
        if (sublist == null) {
            return true;
        }
        if (list == null) {
            return false;
        }
 
        // Recursive case
        if (list.data == sublist.data) {
            return IsSublist(list.next, sublist.next);
        } else {
            return IsSublist(list.next, sublist);
        }
    }
}
 
class Program {
    static void Main(string[] args) {
        // Create the main list
        Node list = new Node(1);
        list.next = new Node(2);
        list.next.next = new Node(1);
        list.next.next.next = new Node(2);
        list.next.next.next.next = new Node(3);
        list.next.next.next.next.next = new Node(4);
 
        // Create the sublist
        Node sublist = new Node(1);
        sublist.next = new Node(2);
        sublist.next.next = new Node(3);
        sublist.next.next.next = new Node(4);
 
        // Check if sublist is present in list
        if (Sublist.IsSublist(list, sublist)) {
            Console.WriteLine("LIST FOUND");
        } else {
            Console.WriteLine("LIST NOT FOUND");
        }
    }
}

Javascript

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}
 
class Sublist {
    static isSublist(list, sublist) {
        // Base cases
        if (sublist == null) {
            return true;
        }
        if (list == null) {
            return false;
        }
 
        // Recursive case
        if (list.data == sublist.data) {
            return Sublist.isSublist(list.next, sublist.next);
        } else {
            return Sublist.isSublist(list.next, sublist);
        }
    }
}
 
// Create the main list
let list = new Node(1);
list.next = new Node(2);
list.next.next = new Node(1);
list.next.next.next = new Node(2);
list.next.next.next.next = new Node(3);
list.next.next.next.next.next = new Node(4);
 
// Create the sublist
let sublist = new Node(1);
sublist.next = new Node(2);
sublist.next.next = new Node(3);
sublist.next.next.next = new Node(4);
 
// Check if sublist is present in list
if (Sublist.isSublist(list, sublist)) {
    console.log("LIST FOUND");
} else {
    console.log("LIST NOT FOUND");
}

Output

LIST FOUND

Time Complexity: O(m*n)
Auxiliary Space: O(m)

Suggest improvement

Linked List representation of Disjoint Set Data Structures

Construct a linked list from 2D matrix

Share your thoughts in the comments

Types of Linked List

Basic operations on Linked List

Easy problems on Linked List

Medium problems on Linked List

Hard problems on Linked List

Types of Linked List

Basic operations on Linked List

Easy problems on Linked List

Medium problems on Linked List

Hard problems on Linked List

Sublist Search (Search a linked list in another list)

Approach 1:

C++

Java

Python3

C#

Javascript

Approach 2: Using recursion

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?