Linked list articles

Sublist Search (Search a linked list in another list)

PrepBytes


This article will explain how to search a linked list in list. sublist search in linked list will definitely help to understand more about linked list. Having a good grasp of Linked Lists can be a huge plus point in a coding interview. Let’s discuss the sublist search algorithm in the linked list.

How To Search A Linked List In Another List

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 3rd index and up to 5th 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 To Search A Linked List In List

  • 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 To Search A Linked List In List

Code Implementation To Search A Linked List In List

#include
#include
#include

struct Node
{
    int data;
    struct Node* next;
};
 
// Returns true if first list is present in second
// list
bool findList(struct Node* first,struct Node* second)
{
    struct 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(struct Node* node)
{
    while (node != NULL)
    {
        printf("%d ", node->data);
        node = node->next;
    }
}
 
// Function to add new node to linked lists
struct Node *newNode(int key)
{
    struct Node* temp = (struct Node*)malloc(sizeof(struct 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*/
    struct Node *a = newNode(1);
    a->next = newNode(2);
    a->next->next = newNode(3);
    a->next->next->next = newNode(4);
 
    struct 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) ? printf("LIST FOUND") :
                    printf("LIST NOT FOUND");
 
    return 0;
}

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

class SublistSearch
{
    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;
    }
    static void printList(Node node)
    {
	    while (node != null)
	    {
		    System.out.printf("%d ", node.data);
		    node = node.next;
	    }
    }
    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)
    {
	    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);

	    if(findList(a, b) == true)
		    System.out.println("LIST FOUND");
	    else
		    System.out.println("LIST NOT FOUND");
    }
}



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 not first and not second:
        return True

    if not first or not second:
        return False

    ptr1 = first
    ptr2 = second

    while ptr2:

        ptr2 = second
        while ptr1:

            if not ptr2:
                return False
            elif ptr1.value == ptr2.value:
                ptr1 = ptr1.next
                ptr2 = ptr2.next

            else:
                break

        if not ptr1:
            return True

        ptr1 = first
        second = second.next
        
    return False

node_a = Node(1)
node_a.next = Node(2)
node_a.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(4)
node_b.next.next.next.next.next = Node(3)

if findList(node_a, node_b):
    print("LIST FOUND")
else:
    print("LIST NOT FOUND")

Output

Found

Time Complexity To Search A Linked List In List: O(M * N), M is the size of lsit1 and N is the size of list2.

This blog gives the best way to search a linked list in list. Having knowledge about data structures like linked list always be the plus point for the interviews. 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.

FAQs

  1. How can I search for data in a linked list?

    2. Implementation to search an element in a linked list:-

    • Initialize head = Null.
    • Add a few items to the Linked List.
    • Take input from the user for the item he wants to search.
    • Linearly traverse the Linked List from head to the end until you hit the null node.

  2. Can linear search be used for linked list?

    3. All traversals of linked lists are in order, so a linear search is the best you can do, with an average case linear in the number of elements.

  3. What is the node in the linked list?

    4. A node is a collection of two sub-parts. A data part that stores the element and a next part that stores the address to the next node.

Leave a Reply

Your email address will not be published. Required fields are marked *

Close

Related Post