Унија и пресек две повезане листе


Ниво тешкоће Средњи
Често питани у 24 * 7 лабораторија за иновације Аццолите амазонка Флипкарт Комли Медиа мицрософт Таки4Суре ВМваре Валмарт Лабс
Хасх Повезана листа сортирање

Дато два повезане листе, креирајте још две повезане листе да бисте добили унију и пресек елемената постојећих листа.

Пример

Улаз:

Листа1: 5 → 9 → 10 → 12 → 14

Листа2: 3 → 5 → 9 → 14 → 21

Излаз:

Листа пресека: 14 → 9 → 5

Унион_лист: 21 → 14 → 12 → 10 → 9 → 5 → 3

objašnjenje: Повезана листа је колекција чворова. Сваки чвор је повезан у низу. Можемо добити раскрсница унија две повезане листе коришћењем неколико метода. Али, ефикасна метода која се користи у овом случају је прва, сортирајте обе повезане листе користећи сортирање спајањем а затим линеарно проверите обе сортиране повезане листе да бисте добили пресек и обједињавање обе повезане листе. Овде је сортирање стапања често пожељно за сортирање повезане листе од осталих алгоритама који имају лош учинак.

Алгоритам

  1. Направите повезану листу тако што ћете објавити главу и следећи показивач на листи.
  2. Уметните елементе у обе листе помоћу функције уметања.
  3. Разврстајте обе повезане листе помоћу алгоритма за обједињавање.
  4. На крају, линеарно скенирајте и сортирану листу да бисте добили унију и пресек листе.

Објашњење

Прво, креирамо чвор стварањем класе Ноде у нашем програму Дакле, како бисмо могли да направимо нашу повезану листу. У нашем програму креирамо две неуређене повезане листе. Након тога сортирамо обе повезане листе помоћу нашег алгоритма за сортирање, а затим креирамо нашу функцију да добијемо унију и пресек наших повезаних листа. Након сортирања обе повезане листе лако их је линеарно скенирати тако да можемо добити унију и пресек наших повезаних листа.

На пример, направите две повезане листе 'лист1' и 'лист2' и у њих уметните елементе помоћу наше класе Ноде у јави или Нодеу структура у ц ++. Након тога проналазимо унију обе повезане листе лист1 и лист2 користећи функцију коју смо направили 'гет_унион' у којој узимамо главу обе повезане листе као аргумент у њој и креирамо привремену листу да сачувамо унију елемент у њему обе листе уз помоћ док петља прва вхиле петља за уметање елемента прве листе у темп. листа и друго за уметање елемента листе 2 у темп. ако их већ нема на листи и коначно смо добили листу испуњену елементима који су уобичајени у обе повезане листе. После тога ћемо употребити нашу методу „гет Интерсецтион“ да бисмо пронашли пресек обе повезане листе, у којој поново узимамо главе обе повезане листе и поново ћемо користити док петља у њега убацити елемент обе повезане листе само ако су чести у обе повезане листе.

Имплементација

Ц ++ програм за унију и пресек две повезане листе

#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

Јава програм за унију и пресек две повезане листе

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

Анализа сложености за спајање и пресек две повезане листе

Сложеност времена

 О (м + н) где "М" „Н“ је број елемената присутних на првој и другој листи.

Сложеност простора

 О (м + н) где "М" „Н“ је број елемената присутних на првој и другој листи.