Байланышкан эки Тизменин бирдиги жана кесилиши  


Кыйынчылык деңгээли орто
Көп суралган 24 * 7 Innovation Labs Accolite Amazon Flipkart Komli Media Microsoft Taxi4Sure VMware Walmart Labs
таштанды Байланышкан тизме сорттоо

Берилген эки байланышкан тизмелер, бар тизмелер элементтеринин биригишин жана кесилишин алуу үчүн дагы эки байланышкан тизмелерди түзүңүз.

мисал  

киргизүү:

Тизме1: 5 → 9 → 10 → 12 → 14

Тизме2: 3 → 5 → 9 → 14 → 21

Output:

Кесилиш_ тизмеси: 14 → 9 → 5

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

Explanation: Байланышкан тизме - бул түйүндөрдүн жыйындысы. Ар бир түйүн ырааттуу түрдө туташтырылган. Биз алабыз кесилишүү жана бирикме бир нече ыкмаларды колдонуу менен эки байланышкан тизмелердин. Бирок, бул учурда натыйжалуу ыкма биринчиден, байланышкан тизмени колдонуп экиге бөлүңүз бириктирүү жана андан кийин эки шилтемеленген тизмелердин кесилишин жана биригишин алуу үчүн иреттелген шилтеме тизмесин экөө тең сызыктуу текшерип чыгыңыз. Бул жерде бириктирилген сортто начар иштеген башка алгоритмдерге караганда, байланышкан тизмени сорттоо үчүн көп учурда артыкчылык берилет.

Algorithm  

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

түшүндүрүү  

Биринчиден, өзүбүздүн Байланыштуу тизмебизди түзсөк болот деп, программабызда Түйүндөр классын түзүп, түйүндү жаратабыз. Биздин программада эки ирээтсиз шилтеме тизмесин түзөбүз. Андан кийин, биз алгоритмдин жардамы менен шилтемеленген тизмени экиге бөлүп, андан кийин шилтелген тизмелерибиздин биригишин жана кесилишин алуу үчүн функцияны түзөбүз. Байланышкан тизмелердин экөөсүн тең бөлүштүргөндөн кийин, аларды бириктирип, шилтемеленген тизмелерибиздин кесилишине ээ болушубуз үчүн, аларды сызыктуу сканерлеп алуу оңой.

ошондой эле
Түйүндү шилтеме берилген тизмеден баш көрсөткүчсүз жок кылыңыз

Мисалы, "list1" жана "list2" деген эки шилтеме тизмесин түзүп, экөөнө тең элементтерди java же түйүндөгү биздин Node классыбыз тарабынан киргизиңиз c ++ түзүмүндө. Андан кийин, биз экөөбүздүн шилтеме берилген тизмелерибиздин тизмесин1 жана list2 'get_union' функциясын колдонуп табабыз, анда эки шилтеменин башын аргумент катары алабыз жана биримдикти сактоо үчүн убактылуу тизме түзөбүз анын жардамы менен эки тизмедеги элемент while цикл first 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) кайда "М" жана "N" тиешелүүлүгүнө жараша биринчи жана экинчи тизмелердеги элементтердин саны.

ошондой эле
Берилген шилтеме тизмесинин аягынан Nth түйүнүн жок кылыңыз

Космостун татаалдыгы

 O (m + n) кайда "М" жана "N" тиешелүүлүгүнө жараша биринчи жана экинчи тизмелердеги элементтердин саны.