બે સortedર્ટ કરેલી સૂચિ મર્જ કરો લિટકોડ સોલ્યુશન્સ


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એડોબ એમેઝોન સફરજન બ્લૂમબર્ગ કેપિટલ વન ફેસબુક Google IBM માઈક્રોસોફ્ટ ઓરેકલ
લિંક્ડ-સૂચિ

લિંક્ડ યાદીઓ તેમના રેખીય ગુણધર્મોમાં એરે જેવા છે. એકંદર સortedર્ટ થયેલ એરે બનાવવા માટે અમે બે સ sર્ટ કરેલી એરે મર્જ કરી શકીએ છીએ. આ સમસ્યામાં, અમારે બે સortedર્ટ લિંક્ડ સૂચિ મર્જ કરવાની છે જગ્યા માં નવી સૂચિ પરત કરવા માટે જેમાં સ whichર્ટ કરેલી ફેશનમાં બંને સૂચિના ઘટકો શામેલ છે.

ઉદાહરણ

બે સortedર્ટ કરેલી સૂચિ મર્જ કરો લિટકોડ સોલ્યુશન્સ

L1 = 1   ->   2   ->   9
L2 = 1   ->   3   ->   4
1 1 2 3 4 9

અભિગમ

તેનો સરળ રીત છે તેનો ઉપયોગ કરવો બે-પોઇન્ટર તકનીક. નવી ખાલી સૂચિ બનાવો. બંને પોઇન્ટર વચ્ચેના નાના તત્વોને જોડો અને અનુરૂપ પોઇન્ટરને વધારશો. આ એક સારો અભિગમ છે પરંતુ તેમાં વધારાની સૂચિ બનાવવાની જરૂર છે જે જગ્યા વાપરે છે.

શ્રેષ્ઠ અભિગમમાં ફક્ત તે કરવા માટે સતત જગ્યાનો વપરાશ કરવો જોઇએ જગ્યા માં વર્ગીકરણ આપણે પુનરાવર્તિત અભિગમને અનુસરી શકીએ છીએ. અમારી પાસે બંને સૂચિઓમાં પહેલાથી ગાંઠો સંગ્રહિત છે. એક નવી સૂચિ નિર્દેશક અને તેના અનુગામી “આગળના નિર્દેશકો"એ મેમરીમાં પૂર્વવ્યાખ્યાયિત ગાંઠો તરફ ધ્યાન દોરવું જોઈએ. આ પ્રક્રિયામાં, અમે બનાવીએ છીએ નં નવા ગાંઠો.

એલ્ગોરિધમ (નિષ્કપટ અભિગમ)

  1. ફંકશન બનાવો મર્જ ટુસ્પોર્ટલિસ્ટ્સ () તે દલીલો તરીકે બે સૂચિ નિર્દેશકો લે છે
  2. જો સૂચિમાંથી કોઈપણ છે નલ, અન્ય એક પરત
  3. બનાવો કામચલાઉ ચલ કે જે બંને સૂચિઓના વડા વચ્ચેના નાના નોડ તરફ નિર્દેશ કરશે
  4. હવે, ઓછામાં ઓછા, અમારા પરિણામમાં એક નોડ જોડાયેલ છે, તેથી એક માથું વધારવું જોઈએ
  5. આ એક સબ પ્રોબ્લેમ બનાવે છે. તેથી, સમાન રિકર્સીવ ફંક્શનને ક callલ કરો અને તેને ટેમ્પમાં જોડો
  6. જો યાદી 1.value <યાદી 2.value
    • કામચલાઉ = નવું લિસ્ટનોડ (સૂચિ 1. મૂલ્ય) , ટેમ્પો-> નેક્સ્ટ = મર્જ ટુસ્વોર્ટલિસ્ટ્સ (સૂચિ 1-> આગળ, સૂચિ 2)
  7. જો સૂચિ 2. મૂલ્ય <= સૂચિ 1. મૂલ્ય
    • કામચલાઉ = નવું લિસ્ટનોડ (સૂચિ 2. મૂલ્ય) , ટેમ્પો-> નેક્સ્ટ = મર્જ ટુસ્વોર્ટલિસ્ટ્સ (સૂચિ 1, સૂચિ 2-> આગળ)
  8. રીટર્ન કામચલાઉ ઇચ્છિત સૂચિ મેળવવા માટે

અલ્ગોરિધમનો (શ્રેષ્ઠ)

  1. એક નવી સૂચિ નિર્દેશક બનાવો જે કહેવાશે ડમી_હેડ.
  2. તેની જાળવણી “કપાળ”(કોપી પોઇન્ટર) જેથી અમે સૂચિને accessક્સેસ કરી શકીએ વડા સરનામું
  3. "આગળના નિર્દેશકો"ડમી_હેડની એવી રીતે ચાલાકી થવી જોઈએ કે તે સૂચિમાં પૂર્વવ્યાખ્યાયિત ગાંઠો તરફ નિર્દેશ કરે l1 અને l2.
  4. ઉપરોક્ત કાર્ય નીચેની રીતોથી કરી શકીએ છીએ.
    • સૂચિઓને તેમના માથાથી પ્રારંભ થતા પોઇંટર્સ સાથે ફરી વળવું ચાલુ રાખો.
    • સૂચિમાંથી એક સંપૂર્ણ રૂપે ન આવે ત્યાં સુધી:
      • બે સૂચિના પોઇંટરોથી નાના મૂલ્યવાન નોડને જોડો ડમી_હેડ, અનુરૂપ પોઇન્ટર વધારવું.
    • હવે, ઓછામાં ઓછું એક નિર્દેશક છે નુ. તેથી, જોડો બિન-નલ ડમી વડા યાદી.
  5. પાછા વડા બનાવટી યાદી છે.

અમલીકરણ

સી ++ પ્રોગ્રામ બે સortedર્ટ કરેલી સૂચિને મર્જ કરવા

નિષ્કપટ અભિગમ

#include <bits/stdc++.h>
using namespace std;

struct listNode
{
    int value;
    listNode* next;

    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};

listNode* mergeTwoSortedLists(listNode* l1 , listNode* l2)
{
    if(!l1)
        return l2;
    if(!l2)
        return l1;

    listNode* temp;
    if(l1->value < l2->value)
    {
        temp = new listNode(l1->value);
        temp->next = mergeTwoSortedLists(l1->next , l2);
    }
    else
    {
        temp = new listNode(l2->value);
        temp->next = mergeTwoSortedLists(l1 , l2->next);
    }

    return temp;
}


void print(listNode* head)
{
    while(head)
    {
        cout << head->value << " ";
        head = head->next;
    }
    cout << '\n';
    return;
}


int main()
{
    listNode* l1 = new listNode(1);
    l1->next = new listNode(2);
    l1->next->next = new listNode(9);

    listNode* l2 = new listNode(1);
    l2->next = new listNode(3);
    l2->next->next = new listNode(4);

    print(mergeTwoSortedLists(l1 , l2));
    return 0;
}

શ્રેષ્ઠ પદ્ધતિ

#include <bits/stdc++.h>
using namespace std;

struct listNode
{
    int value;
    listNode* next;

    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};


listNode* mergeTwoSortedLists(listNode* l1 , listNode* l2)
{
    listNode *dummy_head = new listNode(-1) , *prehead = dummy_head;
    while(l1 && l2)
    {
        if(l1->value < l2->value)
        {
            dummy_head->next = l1;
            l1 = l1->next;
        }
        else
        {
            dummy_head->next = l2;
            l2 = l2->next;
        }
        dummy_head = dummy_head->next;
    }

    dummy_head->next = (l1 ? l1 : l2);
    return prehead->next;
}



void print(listNode* head)
{
    while(head)
    {
        cout << head->value << " ";
        head = head->next;
    }
    cout << '\n';
    return;
}


int main()
{
    listNode* l1 = new listNode(1);
    l1->next = new listNode(2);
    l1->next->next = new listNode(9);

    listNode* l2 = new listNode(1);
    l2->next = new listNode(3);
    l2->next->next = new listNode(4);

    print(mergeTwoSortedLists(l1 , l2));
    return 0;
}
1 1 2 3 4 9

બે સortedર્ટ કરેલી સૂચિને મર્જ કરવા માટે જાવા પ્રોગ્રામ

નિષ્કપટ અભિગમ

class listNode
{
    int value;
    listNode next;

    listNode(int x)
    {
        value = x;
        next = null;
    }
}

class merge_two_sorted_lists
{
    public static void print(listNode head)
    {
        while(head != null)
        {
            System.out.print(head.value + " ");
            head = head.next;
        }
        return;
    }


    public static listNode mergeTwoSortedLists(listNode l1 , listNode l2)
    {
        if(l1 == null)
            return l2;
        if(l2 == null)
            return l1;

        listNode temp;
        if(l1.value < l2.value)
        {
            temp = new listNode(l1.value);
            temp.next = mergeTwoSortedLists(l1.next , l2);
        }
        else
        {
            temp = new listNode(l2.value);
            temp.next = mergeTwoSortedLists(l1 , l2.next);
        }

        return temp;
    }

    public static void main(String args[])
    {
        listNode l1 = new listNode(1);
        l1.next = new listNode(2);
        l1.next.next = new listNode(9);

        listNode l2 = new listNode(1);
        l2.next = new listNode(3);
        l2.next.next = new listNode(4);

        print(mergeTwoSortedLists(l1 , l2));
    }
}

શ્રેષ્ઠ પદ્ધતિ

class listNode
{
    int value;
    listNode next;

    listNode(int x)
    {
        value = x;
        next = null;
    }
}

class merge_two_sorted_lists
{
    public static void print(listNode head)
    {
        while(head != null)
        {
            System.out.print(head.value + " ");
            head = head.next;
        }
        return;
    }


    public static listNode mergeTwoSortedLists(listNode l1 , listNode l2)
    {
        listNode dummy_head = new listNode(-1) , prehead = dummy_head;
        while(l1 != null && l2 != null)
        {
            if(l1.value < l2.value)
            {
                dummy_head.next = l1;
                l1 = l1.next;
            }
            else
            {
                dummy_head.next = l2;
                l2 = l2.next;
            }
            dummy_head = dummy_head.next;
        }

        dummy_head.next = ((l1 != null) ? l1 : l2);
        return prehead.next;
    }

    public static void main(String args[])
    {
        listNode l1 = new listNode(1);
        l1.next = new listNode(2);
        l1.next.next = new listNode(9);

        listNode l2 = new listNode(1);
        l2.next = new listNode(3);
        l2.next.next = new listNode(4);

        print(mergeTwoSortedLists(l1 , l2));
    }
}
1 1 2 3 4 9

જટિલતા વિશ્લેષણ

સમય જટિલતા બે સortedર્ટ કરેલી સૂચિ મર્જ કરવા

ઓ (એન + એમ), જ્યાં N અને M બે સૂચિઓની લંબાઈ છે. અમે બંને સૂચિઓને એકવાર બંને અભિગમોમાં પસાર કરીએ છીએ, તેથી બંને એલ્ગોરિધમ્સ રેખીય છે.

અવકાશ જટિલતા બે સortedર્ટ કરેલી સૂચિ મર્જ કરવા

શ્રેષ્ઠ અભિગમમાં, તે સમજવું મહત્વપૂર્ણ છે કે આપણે ફક્ત પોઇંટરો ચાલાકી. તેથી, ચલ માટે સ્થિર જગ્યા મેમરી વપરાશ માટેના એકાઉન્ટ્સ છે. તેથી, શ્રેષ્ઠ પદ્ધતિની અવકાશ જટિલતા છે ઓ (1). ઓ (એન + એમ) ચર્ચા થયેલ નિષ્કપટ અભિગમમાં અવકાશનો ઉપયોગ થાય છે.