Екі байланыстырылған тізімнің одағы және қиылысы


Күрделілік дәрежесі орта
Жиі кіреді 24 * 7 инновациялық зертханалар Акколит Amazon Flipkart Komli Media Microsoft Такси4Әрине VMware Walmart зертханалары
Hash Байланыстырылған тізім Сұрыптау

Екі байланыстырылған тізімдер, бар тізімдер элементтерінің тоғысуы мен қиылысуы үшін тағы екі байланыстырылған тізімді жасаңыз.

мысал

Кіру:

Тізім1: 5 → 9 → 10 → 12 → 14

Тізім2: 3 → 5 → 9 → 14 → 21

Шығару:

Қиылысу тізімі: 14 → 9 → 5

Union_list: 21 → 14 → 12 → 10 → 9 → 5 → 3

Түсіндіру: Байланыстырылған тізім - бұл түйіндердің жиынтығы. Кез келген түйін дәйектілікпен қосылады. Біз алуға болады қиылыс және одақ бірнеше әдісті қолдану арқылы екі тізімнің тізімі. Бұл жағдайда тиімді әдіс біріншіден, байланыстырылған тізімді пайдаланып сұрыптаңыз біріктіру сұрыптау содан кейін екі байланыстырылған тізімнің қиылысы мен біріктірілуін алу үшін сұрыпталған тізімнің екеуін де сызықтық тексеріңіз. Мұнда біріктіру сұрыпталуы нашар алгоритмдерге қарағанда, байланыстырылған тізімді сұрыптау үшін жиі қолайлы болады.

Алгоритм

  1. Тізімнің басы мен келесі көрсеткішін жариялау арқылы байланыстырылған тізімді құрыңыз.
  2. Функцияны кірістіру арқылы элементтерді тізімге қосыңыз.
  3. Біріктірілген сұрыптау алгоритмін қолдана отырып, екі байланысты тізімді де сұрыптаңыз.
  4. Соңында, тізімнің қосылуын және қиылысын алу үшін сұрыпталған тізімнің екеуін де сызықтық түрде қарап шығыңыз.

Түсіндіру

Біріншіден, біз өзіміздің байланысқан тізімімізді жасай алатындай етіп, өз бағдарламамызда Node класын құру арқылы түйінді жасаймыз. Біздің бағдарламада біз екі реттелмеген тізімді жасаймыз. Осыдан кейін, біз байланыстырылған тізімді де сұрыптау алгоритмі арқылы сұрыптаймыз, содан кейін байланыстырылған тізімдердің бірігуі мен қиылысын алу үшін өз функциямызды құрамыз. Байланыстырылған тізімдердің екеуін де сұрыптағаннан кейін, оларды байланыстырылған тізімдердің қиылысуы мен қиылысуы үшін оларды сызықтық түрде қарап шығу оңай.

Мысалы, 'list1' және 'list2' екі байланыстырылған тізімді құрыңыз және олардың екеуіне де java немесе түйіндегі біздің түйін класы арқылы элементтер енгізіңіз. құрылымы c ++. Осыдан кейін біз «get_union» функциясын қолдану арқылы екі байланыстырылған тізімдердің тізімін1 және list2-ді біріктіреміз, онда екі тізімнің басын аргумент ретінде аламыз және одақты сақтау үшін уақытша тізім жасаймыз. көмегімен екі тізімнің элементі while цикл temp бірінші тізімнің элементін енгізу үшін while while циклі. тізім және екінші тізімге 2 элементті уақытша енгізу үшін. тізім, егер олар тізімде жоқ болса, соңында біз екі тізімде де кездесетін элементтермен толтырылған тізім алдық. Осыдан кейін біз екі қиыстырылған тізімнің қиылысын табу үшін «қиылысты алу» әдісін қолданамыз, сол кезде біз қайтадан екі байланыстырылған тізімнің басшыларын аламыз және қайтадан қолданамыз while цикл оған екі байланыстырылған тізім элементтерін кірістіру үшін, егер олар байланыстырылған тізімнің екеуінде де ортақ болса.

Іске асыру

Екі байланыстырылған тізімнің бірігуіне және қиылысына арналған 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

Екі байланыстырылған тізімдерді біріктіру және қиылысу үшін күрделілікті талдау

Уақыттың күрделілігі

 O (m + n) қайда «M» және «N» сәйкесінше бірінші және екінші тізімдегі элементтер саны.

Ғарыштың күрделілігі

 O (m + n) қайда «M» және «N» сәйкесінше бірінші және екінші тізімдегі элементтер саны.