രണ്ട് ലിങ്ക്ഡ് ലിസ്റ്റുകളുടെ യൂണിയനും ഇന്റർസെക്ഷനും  


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു 24 * 7 ഇന്നൊവേഷൻ ലാബുകൾ അക്കോലൈറ്റ് ആമസോൺ ഫ്ലിപ്പ്കാർട്ട് കോംലി മീഡിയ മൈക്രോസോഫ്റ്റ് ടാക്സി 4 സ്യൂർ വിഎംവെയർ വാൾമാർട്ട് ലാബുകൾ
ഹാഷ് ലിങ്ക്ഡ്-ലിസ്റ്റ് ക്രമപ്പെടുത്തൽ

രണ്ട് നൽകി ലിങ്കുചെയ്‌ത ലിസ്റ്റുകൾ, നിലവിലുള്ള ലിസ്റ്റുകളുടെ ഘടകങ്ങളുടെ യൂണിയനും വിഭജനവും ലഭിക്കുന്നതിന് മറ്റൊരു രണ്ട് ലിങ്കുചെയ്‌ത ലിസ്റ്റുകൾ സൃഷ്ടിക്കുക.

ഉദാഹരണം  

ഇൻപുട്ട്:

ലിസ്റ്റ് 1: 5 → 9 10 → 12 → 14

ലിസ്റ്റ് 2: 3 → 5 9 → 14 → 21

ഔട്ട്പുട്ട്:

ഇന്റർസെക്ഷൻ_ലിസ്റ്റ്: 14 → 9 5

യൂണിയൻ_ലിസ്റ്റ്: 21 → 14 → 12 → 10 → 9 → 5 → 3

വിശദീകരണം: ലിങ്കുചെയ്‌ത ലിസ്റ്റ് നോഡുകളുടെ ശേഖരമാണ്. ഓരോ നോഡും ക്രമത്തിൽ ബന്ധിപ്പിച്ചിരിക്കുന്നു. നമുക്ക് അത് ലഭിക്കും വിഭജനം ഒപ്പം യൂണിയൻ നിരവധി മാർ‌ഗ്ഗങ്ങൾ‌ ഉപയോഗിച്ച് ലിങ്കുചെയ്‌ത രണ്ട് ലിസ്റ്റുകളുടെ. പക്ഷേ, ഈ സാഹചര്യത്തിൽ ഉപയോഗിക്കാനുള്ള കാര്യക്ഷമമായ രീതി ആദ്യം, ലിങ്കുചെയ്‌ത ലിസ്റ്റ് ഉപയോഗിച്ച് അടുക്കുക ലയിപ്പിക്കൽ അടുക്കുക രണ്ട് ലിങ്കുചെയ്‌ത ലിസ്റ്റുകളുടെയും വിഭജനവും യൂണിയനും ലഭിക്കുന്നതിന് അടുക്കിയ ലിങ്കുചെയ്‌ത ലിസ്റ്റ് രേഖീയമായി പരിശോധിക്കുക. മോശമായി പ്രവർത്തിക്കുന്ന മറ്റ് അൽ‌ഗോരിതംസിനേക്കാൾ ലിങ്കുചെയ്‌ത പട്ടിക അടുക്കുന്നതിന് ഇവിടെ ലയനം അടുക്കുന്നു.

അൽഗോരിതം  

  1. പട്ടികയുടെ തലയും അടുത്ത പോയിന്ററും പ്രഖ്യാപിച്ച് ഒരു ലിങ്കുചെയ്‌ത ലിസ്റ്റ് സൃഷ്‌ടിക്കുക.
  2. തിരുകുക func ഉപയോഗിച്ച് രണ്ട് ലിസ്റ്റിലും ഘടകങ്ങൾ ചേർക്കുക.
  3. ലയിപ്പിച്ച അടുക്കൽ അൽ‌ഗോരിതം ഉപയോഗിച്ച് ലിങ്കുചെയ്‌ത രണ്ട് ലിസ്റ്റുകളും അടുക്കുക.
  4. അവസാനമായി, പട്ടികയുടെ യൂണിയനും കവലയും ലഭിക്കുന്നതിന് അടുക്കിയ പട്ടിക രണ്ടും രേഖീയമായി സ്കാൻ ചെയ്യുക.

വിശദീകരണം  

ആദ്യം, ഞങ്ങളുടെ പ്രോഗ്രാമിൽ ഒരു നോഡ് ക്ലാസ് സൃഷ്ടിച്ചുകൊണ്ട് ഞങ്ങൾ ഒരു നോഡ് സൃഷ്ടിക്കുന്നു, അതിനാൽ, ഞങ്ങളുടെ ലിങ്ക്ഡ് ലിസ്റ്റ് സൃഷ്ടിക്കാൻ കഴിയും. ഞങ്ങളുടെ പ്രോഗ്രാമിൽ, ക്രമീകരിക്കാത്ത രണ്ട് ലിങ്ക്ഡ് ലിസ്റ്റ് ഞങ്ങൾ സൃഷ്ടിക്കുന്നു. അതിനുശേഷം, ഞങ്ങളുടെ സോർട്ടിംഗ് അൽ‌ഗോരിതം ഉപയോഗിച്ച് ലിങ്കുചെയ്‌ത ലിസ്റ്റ് രണ്ടും അടുക്കുന്നു, തുടർന്ന് ഞങ്ങളുടെ ലിങ്കുചെയ്‌ത ലിസ്റ്റുകളുടെ യൂണിയനും കവലയും ലഭിക്കുന്നതിന് ഞങ്ങളുടെ പ്രവർത്തനം സൃഷ്ടിക്കുന്നു. ലിങ്കുചെയ്‌ത രണ്ട് ലിസ്റ്റുകളും അടുക്കിയതിനുശേഷം അവ രേഖീയമായി സ്കാൻ ചെയ്യുന്നത് എളുപ്പമാണ്, അങ്ങനെ ഞങ്ങളുടെ ലിങ്കുചെയ്‌ത ലിസ്റ്റുകളുടെ യൂണിയനും വിഭജനവും ലഭിക്കും.

ഇതും കാണുക
ഹെഡ് പോയിന്റർ ഇല്ലാതെ ലിങ്കുചെയ്‌ത ലിസ്റ്റിൽ നിന്ന് ഒരു നോഡ് ഇല്ലാതാക്കുക

ഉദാഹരണത്തിന്, 'ലിസ്റ്റ് 1', 'ലിസ്റ്റ് 2' എന്നീ രണ്ട് ലിങ്കുചെയ്‌ത ലിസ്റ്റുകൾ സൃഷ്‌ടിക്കുക, കൂടാതെ ഇവ രണ്ടിലും ഘടകങ്ങൾ ഞങ്ങളുടെ നോഡ് ക്ലാസ് ജാവയിലോ നോഡിലോ ചേർക്കുക സി ++ ലെ ഘടന. അതിനുശേഷം, ഞങ്ങൾ 'get_union' നിർമ്മിച്ച ഫംഗ്ഷൻ ഉപയോഗിച്ച് ഞങ്ങളുടെ രണ്ട് ലിങ്കുചെയ്ത ലിസ്റ്റുകളുടെ പട്ടിക 1, ലിസ്റ്റ് 2 എന്നിവയുടെ യൂണിയൻ കണ്ടെത്തുന്നു, അതിൽ രണ്ട് ലിങ്ക്ഡ് ലിസ്റ്റിന്റെയും തലയെ ഒരു ആർഗ്യുമെൻറായി എടുക്കുകയും യൂണിയൻ സംരക്ഷിക്കുന്നതിന് ഞങ്ങൾ ഒരു താൽക്കാലിക പട്ടിക സൃഷ്ടിക്കുകയും ചെയ്യുന്നു. രണ്ട് ലിസ്റ്റുകളിലെയും ഘടകം അതിന്റെ സഹായത്തോടെ ലൂപ്പ് സമയത്ത് ആദ്യ പട്ടികയിലെ ഘടകം താൽക്കാലികമായി ചേർക്കുന്നതിനുള്ള ലൂപ്പ്. ലിസ്റ്റും പട്ടികയിലെ 2 ഘടകങ്ങൾ താൽക്കാലികമായി ചേർക്കുന്നതിനുള്ള രണ്ടാമത്തേതും. അവ ഇതിനകം പട്ടികയിൽ‌ ഇല്ലെങ്കിൽ‌ പട്ടികപ്പെടുത്തുക, കൂടാതെ ലിങ്കുചെയ്‌ത രണ്ട് ലിസ്റ്റിലും പൊതുവായുള്ള ഘടകങ്ങൾ‌ നിറഞ്ഞ പട്ടിക ഞങ്ങൾക്ക് ലഭിച്ചു. അതിനുശേഷം, ലിങ്കുചെയ്‌ത രണ്ട് ലിസ്റ്റുകളുടെയും വിഭജനം കണ്ടെത്തുന്നതിന് ഞങ്ങൾ ഞങ്ങളുടെ 'ഇന്റർസെക്ഷൻ നേടുക' രീതി ഉപയോഗിക്കും, അതിൽ ഞങ്ങൾ വീണ്ടും ലിങ്കുചെയ്‌ത രണ്ട് ലിസ്റ്റുകളുടെയും തലകൾ എടുക്കുകയും വീണ്ടും ഉപയോഗിക്കുകയും ചെയ്യും ലൂപ്പ് സമയത്ത് ലിങ്കുചെയ്‌ത ലിസ്റ്റിന്റെ ഒരു ഘടകം ഉൾപ്പെടുത്തുന്നതിന് അതിൽ ലിങ്കുചെയ്‌ത ലിസ്റ്റിൽ പൊതുവായതാണെങ്കിൽ മാത്രം.

നടപ്പിലാക്കൽ  

രണ്ട് ലിങ്കുചെയ്‌ത ലിസ്റ്റുകളുടെ യൂണിയനും ഇന്റർസെക്ഷനുമായുള്ള സി ++ പ്രോഗ്രാം

#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) എവിടെ "M" ഒപ്പം “N” ഒന്നും രണ്ടും ലിസ്റ്റുകളിൽ യഥാക്രമം നിലവിലുള്ള ഘടകങ്ങളുടെ എണ്ണം.

ഇതും കാണുക
തന്നിരിക്കുന്ന ലിങ്കുചെയ്‌ത ലിസ്റ്റിന്റെ അവസാനത്തിൽ നിന്ന് Nth നോഡ് ഇല്ലാതാക്കുക

ബഹിരാകാശ സങ്കീർണ്ണത

 O (m + n) എവിടെ "M" ഒപ്പം “N” ഒന്നും രണ്ടും ലിസ്റ്റുകളിൽ യഥാക്രമം നിലവിലുള്ള ഘടകങ്ങളുടെ എണ്ണം.