פֿאַרבאַנד און ינטערסעקשאַן פון צוויי לינגקט רשימות


שוועריקייט לעוועל מיטל
אָפט געבעטן אין 24 * 7 יננאָוואַטיאָן לאַבס אַקקאָליטע אַמאַזאָן פליפּקאַרט קאָמלי מעדיע מייקראָסאָפֿט Taxi4Sure וומוואַרע וואַלמאַרט לאַבס
האַש לינקעד-רשימה סאָרטינג

געגעבן צוויי לינגקט רשימות, שאַפֿן אן אנדער צוויי לינגקט רשימות צו באַקומען פאַרבאַנד און ינטערסעקשאַן פון די יסודות פון יגזיסטינג רשימות.

בייַשפּיל

ינפּוט:

רשימה 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. לעסאָף, לינעאַרלי יבערקוקן די סאָרטעד רשימה צו באַקומען די פאַרבאַנד און די ינטערסעקשאַן פון דער רשימה.

דערקלערונג

ערשטער, מיר מאַכן אַ נאָדע דורך קריייטינג אַ נאָדע קלאַס אין אונדזער פּראָגראַם אַזוי אַז מיר קענען מאַכן אונדזער לינקעד רשימה. אין אונדזער פּראָגראַם, מיר מאַכן צוויי אַנאָרדערד לינגקט רשימה. דערנאָך מיר סאָרט די לינגקט רשימה מיט אונדזער סאָרטינג אַלגערידאַם און מיר מאַכן אונדזער פֿונקציע צו באַקומען די פאַרבאַנד און די ינטערסעקשאַן פון אונדזער לינגקט רשימות. נאָך סאָרטינג ביידע די לינגקט רשימות, עס איז גרינג צו יבערקוקן זיי לינעאַר אַזוי אַז מיר קענען באַקומען פאַרבאַנד און ינטערסעקשאַן פון אונדזער לינגקט רשימות.

פֿאַר בייַשפּיל, מאַכן צוויי לינגקט רשימות 'ליסט 1' און 'ליסט 2', און אַרייַן אין זיי ביידע עלעמענטן דורך אונדזער נאָדע קלאַס אין Java אָדער נאָדע. סטרוקטור אין C ++. דערנאָך, מיר געפֿינען די פאַרבאַנד פון אונדזער ביידע לינגקט רשימות ליסט 1 און ליסט 2 מיט די פֿונקציע וואָס מיר האָבן געמאכט 'געט_ יוניאָן' אין וואָס מיר נעמען די קאָפּ פון ביידע לינגקט רשימה ווי אַן אַרגומענט אין עס און מיר מאַכן אַ צייַטווייַליק רשימה צו ראַטעווען דעם פאַרבאַנד. עלעמענט אין עס פון ביידע רשימות מיט די הילף פון בשעת שלייף ערשטער בשעת שלייף צו אַרייַנלייגן די עלעמענט פון דער ערשטער רשימה אין טעמפּ. רשימה און רגע צו אַרייַנלייגן די רשימה 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

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

קאַמפּלעקסיטי אַנאַליסיס פֿאַר פֿאַרבאַנד און ינטערסעקשאַן פון צוויי לינקעד רשימות

צייט קאַמפּלעקסיטי

 אָ (m + n) ווו "עם" און “N” זענען די נומער פון עלעמענטן וואָס זענען פאָרשטעלן אין דער ערשטער און רגע רשימות.

ספעיס קאַמפּלעקסיטי

 אָ (m + n) ווו "עם" און “N” זענען די נומער פון עלעמענטן וואָס זענען פאָרשטעלן אין דער ערשטער און רגע רשימות.