Quiz Comment Box

Search

Sublist Search

We are given two linked lists, and our task is to determine whether the second list (sublist) is present or not in the first list (list) in the same order. If the second list is present in the first list in the same order, return true. Else if the second list is not present in the first list, return false.

Example :

Following are the implementation of Sublist Search into programs

                        
   // 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");
}
}      
                        
                         Code 
                    
                        
    public class Bubble {  
        static void print (int a[]) //function to print array elements  
        {  
            int n = a.length;  
            int i;  
            for (i = 0; i < n; i++)  
            {  
                System.out.print(a[i] + " ");  
            }         
        }  
        static void bubbleSort (int a[])    // function to implement bubble sort  
        {  
            int n = a.length;  
            int i, j, temp;  
            for (i = 0; i < n; i++)  
            {  
                for (j = i + 1; j < n; j++)  
                {  
                    if (a[j] < a[i])  
                    {  
                        temp = a[i];  
                        a[i] = a[j];  
                        a[j] = temp;  
                    }  
                }  
            }  
        }  
        public static void main(String[] args) {    
        int a[] = {35, 10, 31, 11, 26};    
        Bubble b1 = new Bubble();  
        System.out.println("Before sorting array elements are - ");    
        b1.print(a);  
        b1.bubbleSort(a);  
        System.out.println();  
        System.out.println("After sorting array elements are - ");    
        b1.print(a);  
            
    }    
    }  
    
                        
                         Code 
                    
                        
   # 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
            else if 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 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")

                        
                         Code 
                    

Sample Output

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

Visualized

Note: For better Visualized Understanding visit our algorithm Visualizer

Visualize
previous

Linear Search