Рубрики

Поиск по списку (Поиск связанного списка в другом списке)

Учитывая два связанных списка, задача состоит в том, чтобы проверить, присутствует ли первый список во втором списке или нет.
Примеры:

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

Алгоритм:
1- Возьмите первый узел второго списка.
2- Начните сопоставлять первый список с этого первого узла.
3- Если все списки совпадают, верните true.
4. Остальное разорвать и снова перенести первый список на первый узел.
5- И перенесите второй список на второй узел.
6- Повторяйте эти шаги, пока любой из связанных списков не станет пустым.
7- Если первый список становится пустым, то список найден иначе нет.

Ниже приведена реализация.

C ++

// C ++ программа для поиска списка во втором списке
#include <bits/stdc++.h>

using namespace std;

  
// Узел связанного списка

struct Node

{

    int data;

    Node* next;

};

  
// Возвращает true, если первый список присутствует во втором
// список

bool findList(Node* first, Node* second)

{

    Node* ptr1 = first, *ptr2 = second;

  

    // Если оба связанных списка пусты, вернуть true

    if (first == NULL && second == NULL)

        return true;

  

    // иначе, если одно пусто, а другое не возвращено

    // ложный

    if ( first == NULL ||

        (first != NULL && second == NULL))

        return false;

  

    // Обходим второй список, выбирая узлы

    // по одному

    while (second != NULL)

    {

        // Инициализируем ptr2 с текущим узлом второго

        ptr2 = second;

  

        // Начать сопоставление первого списка со вторым списком

        while (ptr1 != NULL)

        {

            // Если второй список становится пустым, а первый

            // не возвращаем false

            if (ptr2 == NULL)

                return false;

  

            // Если часть данных одинакова, переходите к следующему

            // обоих списков

            else if (ptr1->data == ptr2->data)

            {

                ptr1 = ptr1->next;

                ptr2 = ptr2->next;

            }

  

            // Если не равно, то разрывать цикл

            else break;

        }

  

        // Возвращаем true, если первый список пройден

        // полностью это означает, что это соответствует.

        if (ptr1 == NULL)

            return true;

  

        // Инициализируем ptr1 снова первым

        ptr1 = first;

  

        // И перейти к следующему узлу второго списка

        second = second->next;

    }

  

    return false;

}

  
/ * Функция для печати узлов в заданном связанном списке * /

void printList(Node* node)

{

    while (node != NULL)

    {

        printf("%d ", node->data);

        node = node->next;

    }

}

  
// Функция добавления нового узла в связанные списки

Node *newNode(int key)

{

    Node *temp = new Node;

    temp-> data= key;

    temp->next = NULL;

    return temp;

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

    / * Давайте создадим два связанных списка для тестирования

    вышеуказанные функции. Созданные списки должны быть

        а: 1-> 2-> 3-> 4

        б: 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 программа для поиска списка во втором списке

import java.util.*;

class GFG 

  
// Узел связанного списка

static class Node 

{

    int data;

    Node next;

};

  
// Возвращает true, если первый список
// присутствует во втором списке

static boolean findList(Node first,

                        Node second)

{

    Node ptr1 = first, ptr2 = second;

  

    // Если оба связанных списка пусты,

    // вернуть true

    if (first == null && second == null)

        return true;

  

    // иначе если один пустой и

    // другого нет, возвращаем false

    if (first == null ||

       (first != null && second == null))

        return false;

  

    // Обходим второй список

    // выбираем узлы один за другим

    while (second != null)

    {

        // Инициализируем ptr2 с помощью

        // текущий узел второго

        ptr2 = second;

  

        // Начать сопоставление первого списка

        // со вторым списком

        while (ptr1 != null)

        {

            // Если второй список становится пустым и

            // сначала нет, потом возвращаем false

            if (ptr2 == null)

                return false;

  

            // Если часть данных одинакова, переходите к следующему

            // обоих списков

            else if (ptr1.data == ptr2.data)

            {

                ptr1 = ptr1.next;

                ptr2 = ptr2.next;

            }

  

            // Если не равно, то разрывать цикл

            else break;

        }

  

        // Возвращаем true, если первый список пройден

        // полностью это означает, что это соответствует.

        if (ptr1 == null)

            return true;

  

        // Инициализируем ptr1 снова первым

        ptr1 = first;

  

        // И перейти к следующему узлу второго списка

        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;

}

  
// Код драйвера

public static void main(String[] args) 

{

    / * Давайте создадим два связанных списка для тестирования

    вышеуказанные функции. Созданные списки должны быть

        а: 1-> 2-> 3-> 4

        б: 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");

}
}

  
// Этот код предоставлен Принчи Сингхом

C #

// C # программа для поиска списка во втором списке

using System;

  

class GFG 

  
// Узел связанного списка

class Node 

{

    public int data;

    public Node next;

};

  
// Возвращает true, если первый список
// присутствует во втором списке

static Boolean findList(Node first,

                        Node second)

{

    Node ptr1 = first, ptr2 = second;

  

    // Если оба связанных списка пусты,

    // вернуть true

    if (first == null && second == null)

        return true;

  

    // иначе если один пустой и

    // другого нет, возвращаем false

    if (first == null ||

       (first != null && second == null))

        return false;

  

    // Обходим второй список

    // выбираем узлы один за другим

    while (second != null)

    {

        // Инициализируем ptr2 с помощью

        // текущий узел второго

        ptr2 = second;

  

        // Начать сопоставление первого списка

        // со вторым списком

        while (ptr1 != null)

        {

            // Если второй список становится пустым и

            // сначала нет, потом возвращаем false

            if (ptr2 == null)

                return false;

  

            // Если часть данных одинакова, переходите к следующему

            // обоих списков

            else if (ptr1.data == ptr2.data)

            {

                ptr1 = ptr1.next;

                ptr2 = ptr2.next;

            }

  

            // Если не равно, то разрывать цикл

            else break;

        }

  

        // Возвращаем true, если первый список пройден

        // полностью это означает, что это соответствует.

        if (ptr1 == null)

            return true;

  

        // Инициализируем ptr1 снова первым

        ptr1 = first;

  

        // И перейти к следующему узлу второго списка

        second = second.next;

    }

    return false;

}

  
/ * Функция для печати узлов
в данном связанном списке * /

static void printList(Node node)

{

    while (node != null)

    {

        Console.Write("{0} ", node.data);

        node = node.next;

    }

}

  
// Функция добавления нового узла в связанные списки

static Node newNode(int key)

{

    Node temp = new Node();

    temp.data= key;

    temp.next = null;

    return temp;

}

  
// Код драйвера

public static void Main(String[] args) 

{

    / * Давайте создадим два связанных списка для тестирования

    вышеуказанные функции. Созданные списки должны быть

        а: 1-> 2-> 3-> 4

        б: 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");

}
}

  
// Этот код предоставлен Rajput-Ji



Выход:

LIST FOUND

Сложность времени: O (m * n), где m — количество узлов во втором списке и n в первом.

Оптимизация:
Приведенный выше код можно оптимизировать, используя дополнительное пространство, т.е. сохраняйте список в две строки и применяйте алгоритм KMP . Обратитесь к https://ide.geeksforgeeks.org/3fXUaV для реализации, предоставленной Nishant Singh .

Эта статья предоставлена Сахилом Чхаброй (Акку) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Поиск по списку (Поиск связанного списка в другом списке)

0.00 (0%) 0 votes