კავშირი და ორი დაკავშირებული სიის გადაკვეთა


Რთული ტური საშუალო
ხშირად ეკითხებიან 24 * 7 ინოვაციის ლაბორატორია თანამოსაყრელი Amazon Flipkart კომლი მედია microsoft ტაქსი 4 VMware Walmart Labs
Hash მიბმული სია დახარისხება

მოცემულია ორი დაკავშირებული სიებიშექმნათ კიდევ ორი ​​დაკავშირებული სია, რომ მიიღოთ არსებული სიების ელემენტები.

მაგალითი

შეყვანის:

სია 1: 5 → 9 → 10 → 12 → 14

სია 2: 3 → 5 → 9 → 14 → 21

გამოყვანის:

კვეთის სია: 14 → 9 → 5

კავშირის_ სია: 21 → 14 → 12 → 10 → 9 → 5 → 3

განმარტება: დაკავშირებული სია არის კვანძების კრებული. ყველა კვანძი თანმიმდევრობით არის დაკავშირებული. ჩვენ შეგვიძლია მივიღოთ კვეთა და კავშირი ორი დაკავშირებული სიის რამდენიმე მეთოდის გამოყენებით. პირველ რიგში, ამ შემთხვევაში გამოსაყენებელი ეფექტური მეთოდია, დაალაგეთ ორივე დაკავშირებული სია შერწყმა დალაგება და შემდეგ ხაზოვნად შეამოწმეთ როგორც დახარისხებული დაკავშირებული სიები, ისე რომ მიიღოთ ორივე დაკავშირებული სიების გადაკვეთა და გაერთიანება. აქ, შერწყმის დალაგება ხშირად სასურველია დაკავშირებული სიის დასალაგებლად, ვიდრე სხვა ალგორითმები, რომლებიც ცუდად ასრულებენ.

ალგორითმი

  1. შექმენით დაკავშირებული სია, სიის თავისა და შემდეგი მაჩვენებლის გამოცხადებით.
  2. ჩადეთ ელემენტები ორივე ჩამონათვალში insert func.
  3. დაალაგეთ ორივე დაკავშირებული სიები შერწყმის დალაგების ალგორითმის გამოყენებით.
  4. დაბოლოს, ხაზობრივად დაასკანირეთ დახარისხებული სია, რომ მიიღოთ სიის გაერთიანება და გადაკვეთა.

განმარტება

პირველ რიგში, ჩვენ ვქმნით კვანძს ჩვენს პროგრამაში Node კლასის შექმნით, რომ შევძლოთ ჩვენი Linked სიის შექმნა. ჩვენს პროგრამაში ჩვენ ვქმნით ორ უწესრიგოდ დაკავშირებულ სიას. ამის შემდეგ, ჩვენ ვალაგებთ ორივე დაკავშირებულ სიას ჩვენი დახარისხების ალგორითმის გამოყენებით და შემდეგ ვქმნით ჩვენს ფუნქციას ჩვენი დაკავშირებული სიების კავშირისა და გადაკვეთის მისაღებად. ორივე დაკავშირებული სიის დალაგების შემდეგ ადვილია მათი ხაზოვანი სკანირება, რათა მივიღოთ კავშირი და ჩვენი დაკავშირებული სიების გადაკვეთა.

მაგალითად, შექმენით ორი დაკავშირებული სია 'list1' და 'list2', და ჩასვით ელემენტები ორივეში ჩვენი Node კლასის მიერ java ან Node სტრუქტურა c ++ - ში. ამის შემდეგ, ჩვენ ვხვდებით ჩვენი ორივე მიბმული სიის სიის 1 და სიის 2 გაერთიანებას იმ ფუნქციის გამოყენებით, რომელიც ჩვენ გავაკეთეთ 'get_union', რომელშიც ჩვენ არგუმენტად ვიღებთ ორივე დაკავშირებული სიის თავს და ვქმნით დროებით ჩამონათვალს კავშირის გადასარჩენად ელემენტი მასში ორივე სიაში დახმარებით ხოლო მარყუჟი პირველი while მარყუჟი პირველი სიის ელემენტის შესატანად დროში. სია და მეორე ჩასასმელად სიაში 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

ჯავა პროგრამა კავშირისა და ორი დაკავშირებული სიის გადაკვეთისთვის

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 (მ + ნ) სადაც "მ" და "ნ" შესაბამისად, პირველ და მეორე სიაში არსებული ელემენტების რაოდენობაა.

სივრცის სირთულე

 O (მ + ნ) სადაც "მ" და "ნ" შესაბამისად, პირველ და მეორე სიაში არსებული ელემენტების რაოდენობაა.