د دوه تړل شوي لیستونو اتحادیه او چورلکه  


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي 24 * 7 د بدعت لیبونه اکولایټ ترلاسه کړئ Amazon فلیپ کارت کوملی میډیا د Microsoft د ټیکسي 4 سوري VMware د وال مارټ لیبز
هاش تړلي لیست ترتیب کول

دوه ورکړل شوي تړلي لیستونه، د شته لیستونو د عناصرو اتحاد او تقاطع ترلاسه کولو لپاره دوه نور تړلي لیستونه جوړ کړئ.

بېلګه  

تفتیش:

لیست 1: 5 → 9 → 10 → 12 → 14

لیست 2: 3 → 5 → 9 → 14 → 21

محصول:

Intersication_list: 14 → 9 → 5

اتحادیه لیست: 21 → 14 → 12 → 10 → 9 → 5 → 3

وضاحت: یو تړلی لیست د نوډونو ټولګه ده. هر نوډ په ترتیب سره وصل دی. موږ دا ترلاسه کولی شو د تقاطع او اتحادیه د ډیری میتودونو په کارولو سره د دوه تړل شوي لیستونو څخه. مګر ، پدې حالت کې د کارولو مؤثر میتود لومړی دی ، په کارولو سره دواړه لړلیک لیست ترتیب کړئ ګډوډ ډول او بیا په ترتیب ډول دواړه ترتیب شوي لړلیک چیک کړئ ترڅو د دواړه لینک لیستونو تقاطع او اتحاد لپاره. دلته ، د یوځای کولو ترتیب اکثرا د نورو الګوریتمونو په پرتله چې د ښه فعالیت ترسره کولو په پرتله د تړل شوي لیست ترتیب کولو لپاره غوره کیږي.

الګوریتم  

  1. د لیست د سر او راتلونکي نښې په اعلانولو سره یو تړلی لیست جوړ کړئ.
  2. د داخل فنک په کارولو سره په دواړه لیست کې عناصر دننه کړئ.
  3. د ضمیم ډول الګوریتم په کارولو دواړه تړلي لیستونه ترتیب کړئ.
  4. په نهایت کې ، په ترتیب سره دواړه ترتیب شوي لیست سکین کړئ ترڅو د لیست اتحادیه او چورلکه ترلاسه کړئ.

تشریح  

لومړی ، موږ زموږ په برنامه کې د نوډ ټولګیو رامینځته کولو سره نوډ رامینځته کوو ، نو موږ کولی شو چې زموږ لینک شوی لیست جوړ کړو. زموږ په برنامه کې ، موږ دوه غیر منظم تړل شوي لیست رامینځته کوو. له هغې وروسته ، موږ د تړلو لست زموږ د ترتیب کولو الګوریتم په کارولو سره تنظیم کوو او بیا موږ زموږ د تړل شوي لیستونو اتحادیه او تقاطع ترلاسه کولو لپاره خپل فعالیت رامینځته کوو. د دواړو تړل شوي لیستونو ترتیب کولو وروسته دا په ساده ډول دوی سکین کول اسانه دي چې موږ کولی شو زموږ د تړل شوي لیستونو اتحادیه او تقاطع ترلاسه کړو.

هم وګوره
د سر نښې پرته لینک شوي لیست څخه نوډ حذف کړئ

د مثال په توګه ، دوه تړلي لیستونه 'list1' او 'list2' جوړ کړئ ، او په جاوا یا نوډ کې زموږ د نوډ ټولګیو لخوا په دواړو کې عناصر داخل کړئ. جوړښت په C ++ کې. له هغې وروسته ، موږ زموږ د دواړه تړل شوي لیستونو لیست 1 او لیست 2 یووالي ومومئ د هغه فنکشن په کارولو سره چې موږ یې 'get_union' جوړ کړ چې په هغه کې موږ د دواړو تړل شوي لیست سر په کې د دلیل په توګه اخلو او موږ د اتحادیې خوندي کولو لپاره لنډمهاله لیست رامینځته کوو د دې په مرسته دواړه لیستونو کې عنصر پداسې حال کې چې لومړی په داسې حال کې چې په لنډ مهاله کې د لومړي لیست عنصر دننه کولو لپاره لوپ کړئ. لیست او دوهم په لیست کې دننه کولو لپاره 2 عنصرونه په لنډ. لیست که دوی دمخه په لیست کې نه وي او په نهایت کې موږ له عناصرو څخه ډک لیست ترلاسه کړ کوم چې په دواړو تړل شوي لیست کې عام دي. له هغې وروسته ، موږ به د دواړه تړل شوي لیستونو تقاطع موندلو لپاره زموږ د 'مفصلو ترلاسه کولو' میتود وکاروو ، پدې کې موږ بیا د دواړو تړل شوي لیستونو سرونه اخلو او بیا به موږ وکاروو پداسې حال کې چې پدې کې د دواړه تړل شوي لیست عنصر داخل کول یوازې هغه وخت چې دوی دواړه لینک شوي لیست کې عام وي.

تطبیق  

د دوه تړل شوي لیستونو اتحادیې او تقاطع لپاره 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" په ترتیب سره په لومړي او دوهم لیستونو کې د عناصرو شمیر شتون لري.