Об'єднання та перетин двох пов'язаних списків  


Рівень складності Medium
Часто запитують у 24 * 7 Інноваційні лабораторії Аколіт Амазонка Flipkart Комлі Медіа Microsoft Таксі4Звичайно VMware Лабораторії Walmart
Мішанина Зв’язаний список Сортування

Дано два пов'язані списки, створіть ще два зв’язані списки, щоб отримати об’єднання та перетин елементів існуючих списків.

Приклад  

Вхідний сигнал:

Список1: 5 → 9 → 10 → 12 → 14

Список2: 3 → 5 → 9 → 14 → 21

вихід:

Список_перетину: 14 → 9 → 5

Union_list: 21 → 14 → 12 → 10 → 9 → 5 → 3

Пояснення: Зв’язаний список - це набір вузлів. Кожен вузол з'єднаний послідовно. Ми можемо отримати перетин і союз двох зв’язаних списків за допомогою декількох методів. Але в цьому випадку ефективним методом буде спочатку сортувати обидва зв’язані списки за допомогою злиття сорту а потім лінійно перевірити відсортований пов'язаний список, щоб отримати перетин і об'єднання обох пов'язаних списків. Тут сортування злиття часто є кращим для сортування пов'язаного списку, ніж інші алгоритми, які працюють погано.

Алгоритм  

  1. Створіть зв’язаний список, оголосивши головку та наступний вказівник списку.
  2. Вставте елементи в обидва списки, використовуючи функцію вставки.
  3. Відсортуйте обидва зв’язані списки за допомогою алгоритму сортування злиття.
  4. Нарешті, лінійно відскануйте відсортований список, щоб отримати об’єднання та перетин списку.

Пояснення  

По-перше, ми створюємо вузол, створюючи клас Node у нашій програмі Отже, щоб ми могли створити наш пов'язаний список. У нашій програмі ми створюємо два невпорядкованих пов'язаних списку. Після цього ми сортуємо обидва зв’язані списки за допомогою нашого алгоритму сортування, а потім створюємо нашу функцію для отримання об’єднання та перетину зв’язаних списків. Після сортування обох зв'язаних списків легко відсканувати їх лінійно, щоб ми могли отримати об'єднання та перетин наших зв'язаних списків.

Дивись також
Видалити вузол зі зв’язаного списку без вказівника на голову

Наприклад, створіть два пов'язаних списки 'list1' і 'list2' і вставте елементи в обидва з них за допомогою нашого класу Node в Java або Node Структура в C ++. Після цього ми знаходимо об’єднання обох зв’язаних списків list1 та list2, використовуючи функцію, яку ми створили 'get_union', в якій ми беремо голову обох пов'язаних списків як аргумент у ній і створюємо тимчасовий список для збереження об'єднання елемента в обох списках за допомогою поки петля цикл first while, щоб вставити елемент першого списку в temp. list і другий для вставки списку 2 елементів у temp. якщо їх ще немає в списку, і нарешті ми отримали список, заповнений елементами, які є загальними в обох зв’язаних списках. Після цього ми використаємо наш метод 'get Intersection', щоб знайти перетин обох пов'язаних списків, в якому ми знову беремо голови обох пов'язаних списків і знову використовуємо поки петля в нього вставити елемент обох пов'язаних списків, лише якщо вони спільні в обох пов'язаних списках.

Реалізація  

Програма C ++ для об'єднання та перетину двох пов'язаних списків

#include<iostream>
#include<stdlib.h>
using namespace std;

struct Node
{
    int value;
    struct Node* next;
};

void insert(struct Node** head, int new_value)
{
    struct Node* NewNode = (struct Node*) malloc(sizeof(struct Node));

    NewNode->value = new_value;

    NewNode->next = (*head);

    (*head) = NewNode;
}

void Front_Back(struct Node* source, struct Node** front, struct Node** back)
{
    struct Node* fast;
    struct Node* slow;
    if (source==NULL || source->next==NULL)
    {
        *front = source;
        *back = NULL;
    }
    else
    {
        slow = source;
        fast = source->next;

        while (fast != NULL)
        {
            fast = fast->next;
            if (fast != NULL)
            {
                slow = slow->next;
                fast = fast->next;
            }
        }

        *front = source;
        *back = slow->next;
        slow->next = NULL;
    }
}

struct Node* Sort_merge(struct Node* fst, struct Node* sec)
{
    struct Node* result = NULL;

    if (fst == NULL)
        return(sec);
    else if (sec==NULL)
        return(fst);

    if (fst->value <= sec->value)
    {
        result = fst;
        result->next = Sort_merge(fst->next, sec);
    }
    else
    {
        result = sec;
        result->next = Sort_merge(fst, sec->next);
    }
    return(result);
}

void Sort(struct Node** head)
{
    struct Node *head_node= *head;
    struct Node *a, *b;

    if ((head_node == NULL) || (head_node->next == NULL))
        return;

    Front_Back(head_node, &a, &b);

    Sort(&a);
    Sort(&b);

    *head = Sort_merge(a, b);
}

struct Node *get_Union(struct Node *head1, struct Node *head2)
{
    struct Node *result = NULL;
    struct Node *t1 = head1, *t2 = head2;

    while (t1 != NULL && t2 != NULL)
    {
        if (t1->value < t2->value)
        {
            insert(&result, t1->value);
            t1 = t1->next;
        }

        else if (t1->value>t2->value)
        {
            insert(&result, t2->value);
            t2 = t2->next;
        }
        else
        {
            insert(&result, t2->value);
            t1 = t1->next;
            t2 = t2->next;
        }
    }

    while (t1 != NULL)
    {
        insert(&result, t1->value);
        t1 = t1->next;
    }
    while (t2 != NULL)
    {
        insert(&result, t2->value);
        t2 = t2->next;
    }

    return result;
}

struct Node *get_Intersection(struct Node *head1, struct Node *head2)
{
    struct Node *result = NULL;
    struct Node *t1 = head1, *t2 = head2;

    while (t1 != NULL && t2 != NULL)
    {
        if (t1->value < t2->value)
            t1 = t1->next;

        else if (t1->value > t2->value)
            t2 = t2->next;

        else
        {
            insert(&result, t2->value);

            t1 = t1->next;
            t2 = t2->next;
        }
    }

    return result;
}

void printList (struct Node *node)
{
    while (node != NULL)
    {
        cout<<node->value << " ";
        node = node->next;
    }
    cout<<endl;
}

int main()
{
    struct Node* head1 = NULL;
    struct Node* head2 = NULL;
    struct Node* intersection_list = NULL;
    struct Node* union_list = NULL;

    insert(&head1, 20);
    insert(&head1, 4);
    insert(&head1, 15);
    insert(&head1, 10);
    insert(&head1, 11);

    insert(&head2, 10);
    insert(&head2, 2);
    insert(&head2, 4);
    insert(&head2, 8);

    Sort(&head1);
    Sort(&head2);

    intersection_list = get_Intersection(head1, head2);
    union_list = get_Union(head1, head2);

    cout<<"First list is \n";
    printList(head1);

    cout<<"\nSecond list is \n";
    printList(head2);

    cout<<"\nIntersection list is \n";
    printList(intersection_list);

    cout<<"\nUnion list is \n";
    printList(union_list);

    return 0;
}
First list is
4 10 11 15 20

Second list is
2 4 8 10

Intersection list is
10 4

Union list is
20 15 11 10 8 4 2

Програма Java для об'єднання та перетину двох пов'язаних списків

class Solution1
{
    Node head;


    class Node
    {
        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }


    void get_union(Node hd1, Node hd2)
    {
        Node t1 = hd1, t2 = hd2;


        while (t1 != null)
        {
            insert(t1.data);
            t1 = t1.next;
        }


        while (t2 != null)
        {
            if (!is_Present(head, t2.data))
                insert(t2.data);
            t2 = t2.next;
        }
    }

    void get_intrSection(Node hd1, Node hd2)
    {
        Node rst = null;
        Node t1 = hd1;


        while (t1 != null)
        {
            if (is_Present(hd2, t1.data))
                insert(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 insert(int new_data)
    {

        Node new_node = new Node(new_data);


        new_node.next = head;


        head = new_node;
    }


    boolean is_Present(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[])
    {
        Solution1 llist1 = new Solution1();
        Solution1 llist2 = new Solution1();
        Solution1 unin = new Solution1();
        Solution1 intersecn = new Solution1();


        llist1.insert(20);
        llist1.insert(4);
        llist1.insert(15);
        llist1.insert(10);


        llist2.insert(10);
        llist2.insert(2);
        llist2.insert(4);
        llist2.insert(8);

        intersecn.get_intrSection(llist1.head, llist2.head);
        unin.get_union(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 (m + n) де "М" і "N" - кількість елементів, присутніх у першому та другому списках відповідно.

Дивись також
Видаліть N-ий вузол з кінця даного пов'язаного списку

Складність простору

 O (m + n) де "М" і "N" - кількість елементів, присутніх у першому та другому списках відповідно.