Рубрики

Объединение и пересечение двух связанных списков

Имея два связанных списка, создайте списки объединения и пересечения, которые содержат объединение и пересечение элементов, присутствующих в данных списках. Порядок элементов в выходных списках не имеет значения.

Пример:

Input:
   List1: 10->15->4->20
   lsit2:  8->4->2->10
Output:
   Intersection List: 4->10
   Union List: 2->8->20->4->15->10

Способ 1 (простой)
Ниже приведены простые алгоритмы для получения списков объединения и пересечения соответственно.

Пересечение (list1, list2)
Инициализируйте список результатов как NULL. Пройдите по list1 и найдите каждый его элемент в list2, если этот элемент присутствует в list2, затем добавьте элемент в result.

Unio n (list1, list2):
Инициализируйте список результатов как NULL. Пройдите через list1 и добавьте все его элементы к результату.
Пересечь список2. Если элемент list2 уже присутствует в результате, не вставляйте его в результат, иначе вставьте.

Этот метод предполагает, что в данных списках нет дубликатов.

Спасибо Шеху за предложение этого метода. Ниже приведены реализации этого метода на C и Java.

C / C ++

// C / C ++ программа для поиска объединения и пересечения двух несортированных
// связанные списки
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
/ * Узел списка ссылок * /

struct Node

{

    int data;

    struct Node* next;

};

  
/ * Утилита для вставки узла в начале

   связанный список * /

void push(struct Node** head_ref, int new_data);

  
/ * Утилита для проверки наличия данных в списке * /

bool isPresent(struct Node *head, int data);

  
/ * Функция для получения объединения двух связанных списков head1 и head2 * /

struct Node *getUnion(struct Node *head1, struct Node *head2)

{

    struct Node *result = NULL;

    struct Node *t1 = head1, *t2 = head2;

  

    // Вставляем все элементы list1 в список результатов

    while (t1 != NULL)

    {

        push(&result, t1->data);

        t1 = t1->next;

    }

  

    // Вставляем те элементы list2, которые не являются

    // присутствует в списке результатов

    while (t2 != NULL)

    {

        if (!isPresent(result, t2->data))

            push(&result, t2->data);

        t2 = t2->next;

    }

  

    return result;

}

  
/ * Функция для пересечения двух связанных списков

  голова1 и голова2 * /

struct Node *getIntersection(struct Node *head1, 

                              struct Node *head2)

{

    struct Node *result = NULL;

    struct Node *t1 = head1;

  

    // Обходим список list1 и ищем каждый его элемент в

    // list2. Если элемент присутствует в списке 2, то

    // вставляем элемент в результат

    while (t1 != NULL)

    {

        if (isPresent(head2, t1->data))

            push (&result, t1->data);

        t1 = t1->next;

    }

  

    return result;

}

  
/ * Полезная функция для вставки узла в начале связанного списка * /

void push (struct Node** head_ref, int new_data)

{

    / * выделить узел * /

    struct Node* new_node =

        (struct Node*) malloc(sizeof(struct Node));

  

    / * вставить данные * /

    new_node->data = new_data;

  

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

    new_node->next = (*head_ref);

  

    / * переместить голову, чтобы указать на новый узел * /

    (*head_ref) = new_node;

}

  
/ * Утилита для печати связанного списка * /

void printList (struct Node *node)

{

    while (node != NULL)

    {

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

        node = node->next;

    }

}

  
/ * Вспомогательная функция, которая возвращает true, если данные

   присутствует в связанном списке, иначе возвращает false * /

bool isPresent (struct Node *head, int data)

{

    struct Node *t = head;

    while (t != NULL)

    {

        if (t->data == data)

            return 1;

        t = t->next;

    }

    return 0;

}

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

int main()

{

    / * Начнем с пустого списка * /

    struct Node* head1 = NULL;

    struct Node* head2 = NULL;

    struct Node* intersecn = NULL;

    struct Node* unin = NULL;

  

    / * создать связанный лит 10-> 15-> 5-> 20 * /

    push (&head1, 20);

    push (&head1, 4);

    push (&head1, 15);

    push (&head1, 10);

  

    / * создать связанный лист 8-> 4-> 2-> 10 * /

    push (&head2, 10);

    push (&head2, 2);

    push (&head2, 4);

    push (&head2, 8);

  

    intersecn = getIntersection (head1, head2);

    unin = getUnion (head1, head2);

  

    printf ("\n First list is \n");

    printList (head1);

  

    printf ("\n Second list is \n");

    printList (head2);

  

    printf ("\n Intersection list is \n");

    printList (intersecn);

  

    printf ("\n Union list is \n");

    printList (unin);

  

    return 0;

}

Джава

// Java программа для поиска объединения и пересечения двух несортированных
// связанные списки

class LinkedList

{

    Node head;  // заголовок списка

  

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

    class Node

    {

        int data;

        Node next;

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

    / * Функция для получения объединения 2 связанных списков * /

    void getUnion(Node head1, Node head2)

    {

        Node t1 = head1, t2 = head2;

  

        // вставляем все элементы list1 в результат

        while (t1 != null)

        {

            push(t1.data);

            t1 = t1.next;

        }

  

        // вставляем те элементы list2, которых нет

        while (t2 != null)

        {

            if (!isPresent(head, t2.data))

                push(t2.data);

            t2 = t2.next;

        }

    }

  

    void getIntersection(Node head1, Node head2)

    {

        Node result = null;

        Node t1 = head1;

  

        // Переходим по list1 и ищем каждый его элемент в list2.

        // Если элемент присутствует в списке 2, вставьте

        // элемент к результату

        while (t1 != null)

        {

            if (isPresent(head2, t1.data))

                push(t1.data);

            t1 = t1.next;

        }

    }

  

    / * Утилита для печати списка * /

    void printList()

    {

        Node temp = head;

        while(temp != null)

        {

            System.out.print(temp.data+" ");

            temp = temp.next;

        }

        System.out.println();

    }

  

  

    / * Вставляет узел в начале связанного списка * /

    void push(int new_data)

    {

        / * 1 & 2: выделить узел &

                  Введите данные * /

        Node new_node = new Node(new_data);

  

        / * 3. Сделать следующий новый узел в качестве головы * /

        new_node.next = head;

  

        / * 4. Переместить голову, чтобы указать на новый узел * /

        head = new_node;

    }

  

  

    / * Утилита, которая возвращает true, если данные присутствуют

       в связанном списке еще вернуть false * /

    boolean isPresent (Node head, int data)

    {

        Node t = head;

        while (t != null)

        {

            if (t.data == data)

                return true;

            t = t.next;

        }

        return false;

    }

  

  

    / * Сушилка для тестирования вышеуказанных функций * /

    public static void main(String args[])

    {

        LinkedList llist1 = new LinkedList();

        LinkedList llist2 = new LinkedList();

        LinkedList unin = new LinkedList();

        LinkedList intersecn = new LinkedList();

  

        / * создать связанный лит 10-> 15-> 5-> 20 * /

        llist1.push(20);

        llist1.push(4);

        llist1.push(15);

        llist1.push(10);

  

        / * создать связанный лист 8-> 4-> 2-> 10 * /

        llist2.push(10);

        llist2.push(2);

        llist2.push(4);

        llist2.push(8);

  

        intersecn.getIntersection(llist1.head, llist2.head);

        unin.getUnion(llist1.head, llist2.head);

  

        System.out.println("First List is");

        llist1.printList();

  

        System.out.println("Second List is");

        llist2.printList();

  

        System.out.println("Intersection List is");

        intersecn.printList();

  

        System.out.println("Union List is");

        unin.printList();

    }

} / * Этот код предоставлен Раджатом Мишрой * /


Выход:

 First list is
10 15 4 20
 Second list is
8 4 2 10
 Intersection list is
4 10
 Union list is
2 8 20 4 15 10

Сложность времени: O (mn) для операций объединения и пересечения. Здесь m — количество элементов в первом списке, а n — количество элементов во втором списке.

Способ 2 (использовать сортировку слиянием)
В этом методе алгоритмы для объединения и пересечения очень похожи. Сначала мы сортируем заданные списки, затем проходим отсортированные списки, чтобы получить объединение и пересечение.
Ниже приведены шаги, которые необходимо выполнить, чтобы получить списки объединений и пересечений.

1) Сортировка первого связанного списка с помощью сортировки слиянием. Этот шаг занимает время O (mLogm). Обратитесь к этому сообщению для деталей этого шага.
2) Сортировка второго связанного списка с помощью сортировки слиянием. Этот шаг занимает O (nLogn) время. Обратитесь к этому сообщению для деталей этого шага.
3) Линейно сканируйте оба отсортированных списка, чтобы получить объединение и пересечение. Этот шаг занимает O (m + n) времени. Этот шаг может быть реализован с использованием того же алгоритма, что и рассмотренный здесь алгоритм отсортированных массивов.

Временная сложность этого метода составляет O (mLogm + nLogn), что лучше, чем временная сложность метода 1.

Способ 3 (использовать хеширование)
Союз (список1, список2)
Инициализируйте список результатов как NULL и создайте пустую хеш-таблицу. Обходите оба списка по одному, для каждого посещаемого элемента ищите элемент в хеш-таблице. Если элемент отсутствует, вставьте элемент в список результатов. Если элемент присутствует, то игнорируйте его.

Пересечение (list1, list2)
Инициализируйте список результатов как NULL и создайте пустую хеш-таблицу. Пересечь список1. Для каждого элемента, посещаемого в list1, вставьте элемент в хеш-таблицу. Перейдите list2, для каждого элемента, посещаемого в list2, посмотрите элемент в хэш-таблице. Если элемент присутствует, вставьте элемент в список результатов. Если элемент отсутствует, игнорируйте его.

Оба вышеуказанных метода предполагают, что дубликатов нет.

// Java-код для объединения и пересечения двух
// Связанные списки

import java.util.HashMap;

import java.util.HashSet;

  

class LinkedList {

    Node head; // заголовок списка

      

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

    class Node

    {

        int data;

        Node next;

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

          

    / * Утилита для печати списка * /

    void printList()

    {

        Node temp = head;

        while(temp != null)

        {

            System.out.print(temp.data+" ");

            temp = temp.next;

        }

        System.out.println();

    }

      

    / * Вставляет узел в начале связанного списка * /

    void push(int new_data)

    {

        / * 1 & 2: выделить узел &

        Введите данные * /

        Node new_node = new Node(new_data);

      

        / * 3. Сделать следующий новый узел в качестве головы * /

        new_node.next = head;

      

        / * 4. Переместить голову, чтобы указать на новый узел * /

        head = new_node;

    }

      

    public void append(int new_data)

    {

        if(this.head == null)

        {

            Node n = new Node(new_data);

            this.head = n;

            return;

        }

        Node n1 = this.head;

        Node n2 = new Node(new_data);

        while(n1.next != null)

        {

            n1 = n1.next;

        }

              

        n1.next = n2;

        n2.next = null;

    }

          

    / * Утилита, которая возвращает true, если данные

    присутствует в связанном списке, иначе возвращает false * /

    boolean isPresent (Node head, int data)

    {

        Node t = head;

        while (t != null)

        {

            if (t.data == data)

                return true;

            t = t.next;

        }

        return false;

    }

      
LinkedList getIntersection(Node head1, Node head2)
{

    HashSet<Integer> hset = new HashSet<>();

    Node n1 = head1;

    Node n2 = head2;

    LinkedList result = new LinkedList();

      

    // цикл хранит все элементы list1 в hset

    while(n1 != null)

    {

        if(hset.contains(n1.data))

        {

            hset.add(n1.data);

        }

        else

        {

            hset.add(n1.data);

        }

        n1 = n1.next;

    }

      

    // Для каждого элемента list2, присутствующего в hset

    // цикл вставляет элемент в результат

    while(n2 != null)

    {

        if(hset.contains(n2.data))

        {

            result.push(n2.data);

        }

        n2 = n2.next;

    }

    return result;

}

  
LinkedList getUnion(Node head1, Node head2)
{

    // HashMap, который будет хранить

    // элементы списков с их количеством

    HashMap<Integer, Integer> hmap = new HashMap<>();

    Node n1 = head1;

    Node n2 = head2;

    LinkedList result = new LinkedList();

      

    // цикл вставляет элементы и количество

    // этот элемент list1 в hmap

    while(n1 != null)

    {

        if(hmap.containsKey(n1.data))

        {

            int val = hmap.get(n1.data);

            hmap.put(n1.data, val + 1);

        }

        else

        {

            hmap.put(n1.data, 1);

        }

        n1 = n1.next;

    }

      

    // цикл дополнительно добавляет элементы list2 с

    // их количество в hmap

    while(n2 != null)

    {

        if(hmap.containsKey(n2.data))

        {

            int val = hmap.get(n2.data);

            hmap.put(n2.data, val + 1);

        }

        else

        {

            hmap.put(n2.data, 1);

        }

        n2 = n2.next; 

    }

      

    // В конце концов добавляем все элементы

    // в результат, который присутствует в hmap

    for(int a:hmap.keySet())

    {

        result.append(a);

    }

    return result;

}

  

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

    public static void main(String args[])

    {

        LinkedList llist1 = new LinkedList();

        LinkedList llist2 = new LinkedList();

        LinkedList union = new LinkedList();

        LinkedList intersection = new LinkedList();

  

        / * создать связанный список 10-> 15-> 4-> 20 * /

        llist1.push(20);

        llist1.push(4);

        llist1.push(15);

        llist1.push(10);

  

        / * создать связанный список 8-> 4-> 2-> 10 * /

        llist2.push(10);

        llist2.push(2);

        llist2.push(4);

        llist2.push(8);

  

        intersection = intersection.getIntersection(llist1.head,

                                                  llist2.head);

        union=union.getUnion(llist1.head, llist2.head);

  

        System.out.println("First List is");

        llist1.printList();

  

        System.out.println("Second List is");

        llist2.printList();

  

        System.out.println("Intersection List is");

        intersection.printList();

  

        System.out.println("Union List is");

        union.printList();

    }     

}
// Этот код предоставлен Камалем Равалом

Выход:

First List is
10 15 4 20 
Second List is
8 4 2 10 
Intersection List is
10 4 
Union List is
2 4 20 8 10 15 

Временная сложность этого метода зависит от используемой техники хеширования и распределения элементов во входных списках. На практике этот подход может оказаться лучше, чем вышеуказанные 2 метода.

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

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

Объединение и пересечение двух связанных списков

0.00 (0%) 0 votes