اتحادیه و تقاطع دو لیست پیوندی  


سطح دشواری متوسط
اغلب در 24 * 7 آزمایشگاه نوآوری همبستگی آمازون Flipkart رسانه کوملی مایکروسافت Taxi4Sure آموزش VMware آزمایشگاه های والمارت
مخلوط لینک شده مرتب سازی

با توجه به دو لیست های مرتبط، برای بدست آوردن اتحادیه و تلاقی عناصر لیست های موجود ، دو لیست پیوند داده شده دیگر ایجاد کنید.

مثال  

ورودی:

لیست 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 و list2 خود را با استفاده از تابعی که "get_union" ایجاد کردیم پیدا می کنیم که در آن سر هر دو لیست پیوندی را به عنوان آرگومان در آن قرار می دهیم و یک لیست موقت برای ذخیره اتحادیه ایجاد می کنیم. عنصر موجود در آن از هر دو لیست با کمک حلقه در حالی که اولین حلقه while برای درج عنصر لیست اول در دما. لیست و دوم برای قرار دادن عناصر لیست 2 در دما. اگر آنها قبلاً در این لیست نبودند ، لیست کنید و در آخر ما لیستی پر از عناصری را پیدا کردیم که در هر دو لیست پیوندی رایج است. پس از آن ، ما از روش "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 (m + n) جایی که "متر" و "n" به ترتیب تعداد عناصر موجود در لیست اول و دوم هستند.

همچنین مشاهده کنید
گره Nth را از انتهای لیست پیوند داده شده حذف کنید

پیچیدگی فضا

 O (m + n) جایی که "متر" و "n" به ترتیب تعداد عناصر موجود در لیست اول و دوم هستند.