වර්ග කළ ලැයිස්තු දෙකක් ලීට්කෝඩ් විසඳුම් ඒකාබද්ධ කරන්න  


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇෙබෝ ඇමේසන් Apple ජංගම දුරකථන බ්ලූම්බර්ග් ප්රාග්ධන එක් ෆේස්බුක් ගූගල් IBM ආයතනය මයික්රොසොෆ්ට් ඔරකල්
ඇල්ගොරිතම කේතීකරණය සම්මුඛ පරීක්ෂණ සම්මුඛ සාකච්ඡා ලීට්කෝඩ් LeetCodeSolutions සම්බන්ධිත ලැයිස්තුව

සම්බන්ධිත ලැයිස්තු ඒවායේ රේඛීය ගුණාංගවල අරා හා සමාන ය. අපට වර්ග කළ අරා දෙකක් ඒකාබද්ධ කර සමස්ත වර්ග කළ අරාවක් සෑදිය හැකිය. මෙම ගැටළුවේදී, අප විසින් වර්ග කළ සම්බන්ධිත ලැයිස්තු දෙකක් ඒකාබද්ධ කළ යුතුය ස්ථානගත වී ඇත ලැයිස්තු දෙකේම අංග අඩංගු නව ලැයිස්තුවක් නැවත වර්ග කිරීම සඳහා.

උදාහරණයක්  

වර්ග කළ ලැයිස්තු දෙකක් ලීට්කෝඩ් විසඳුම් ඒකාබද්ධ කරන්නපින්

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

ප්රවේශය  

එය කළ හැකි සරලම ක්‍රමය වනුයේ ද්වි-දර්ශකය තාක්ෂණය. නව හිස් ලැයිස්තුවක් සාදන්න. දර්ශක දෙක අතර කුඩා මූලද්‍රව්‍ය එකතු කර අනුරූප දර්ශකය වැඩි කරන්න. මෙය හොඳ ප්‍රවේශයක් වන නමුත් අවකාශය පරිභෝජනය කරන අතිරේක ලැයිස්තුවක් නිර්මාණය කිරීම අවශ්‍ය වේ.

ප්‍රශස්ත ප්‍රවේශය නියත අවකාශය පරිභෝජනය කළ යුත්තේ එය සිදු කිරීම සඳහා පමණි ස්ථානයේ වර්ග කිරීම. අපට පුනරාවර්තන ප්‍රවේශය අනුගමනය කළ හැකිය. ලැයිස්තු දෙකෙහිම අපි දැනටමත් නෝඩ් ගබඩා කර ඇත. නව ලැයිස්තු දර්ශකයක් සහ ඉන් පසුව ඇති වන “ඊළඟ දර්ශකයන්”මතකයේ ඇති පූර්ව නිශ්චිත නෝඩ් වෙත යොමු විය යුතුය. මෙම ක්‍රියාවලියේදී අපි නිර්මාණය කරමු නැත නව නෝඩ්.

ඇල්ගොරිතම (බොළඳ ප්‍රවේශය)  

  1. ශ්‍රිතයක් සාදන්න mergeTwoSortedLists () එය ලැයිස්තු දර්ශක දෙකක් තර්ක ලෙස ගනී
  2. එක් ලැයිස්තුවක් නම් NULL අනිත් එක ආපසු දෙන්න
  3. සාදන්න තාවකාලික ලැයිස්තු දෙකේම ප්‍රධානීන් අතර කුඩා නෝඩයට යොමු වන විචල්‍යය
  4. දැන්, අවම වශයෙන්, එක් නෝඩයක් අපගේ ප්‍රති result ලයට එකතු කර ඇති බැවින් එක් හිසක් වැඩි කළ යුතුය
  5. මෙය උපප්‍රශ්නයක් නිර්මාණය කරයි. එබැවින්, එකම පුනරාවර්තන ශ්‍රිතය අමතා එය තාවකාලිකව එකතු කරන්න
  6. List1.value <List2.value නම්
    • උෂ්ණත්වය = නව ListNode (List1.value) , temp-> next = mergeTwoSortedLists (List1-> ඊළඟ, List2)
  7. List2.value <= List1.value නම්
    • උෂ්ණත්වය = නව ListNode (List2.value) , temp-> next = mergeTwoSortedLists (List1, List2-> ඊළඟ)
  8. ආපසු තාවකාලික අපේක්ෂිත ලැයිස්තුව ලබා ගැනීමට
මෙයද බලන්න
අන්තරාන්තර ලීට්කෝඩ් විසඳුම ඇතුළු කරන්න

ඇල්ගොරිතම (ප්‍රශස්ත)  

  1. නව ලැයිස්තු දර්ශකයක් සාදන්න ව්‍යාජ හිස.
  2. එහි “පෙරමුන”(පිටපත් දර්ශකය පිටපත් කරන්න) එවිට අපට ලැයිස්තුවට ප්‍රවේශ විය හැකිය හිස ලිපිනය.
  3. එම "ඊළඟ දර්ශකයන්”ඩම්මි_හෙඩ් හි ලැයිස්තුගත කර ඇති පූර්ව නිශ්චිත නෝඩ් වෙත යොමු වන ආකාරයට හැසිරවිය යුතුය l1 සහ l2.
  4. ඉහත කාර්යය අපට පහත ආකාරවලින් කළ හැකිය:
    • ඔවුන්ගේ හිසෙන් ආරම්භ වන දර්ශකයන් සමඟ ලැයිස්තු නැවත සඳහන් කරන්න.
    • එක් ලැයිස්තුවක් මුළුමනින්ම ගමන් නොකරන්නේ නම්:
      • ලැයිස්තු දර්ශක දෙකේ සිට කුඩා වටිනාකමින් යුත් නෝඩය එකතු කරන්න ව්‍යාජ හිස, අනුරූප දර්ශකය වැඩි කිරීම.
    • දැන්, අවම වශයෙන් එක් දර්ශකයක් වේ ශුන්‍ය එබැවින්, එකතු කරන්න ශුන්‍ය නොවන ව්‍යාජ හිසට ලැයිස්තු ගත කරන්න.
  5. ආපසු හිස ව්‍යාජ ලැයිස්තුවේ.

ක්රියාත්මක කිරීම  

වර්ග කළ ලැයිස්තු දෙකක් ඒකාබද්ධ කිරීම සඳහා සී ++ වැඩසටහන

බොළඳ ප්‍රවේශය

#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

වර්ග කළ ලැයිස්තු දෙකක් ඒකාබද්ධ කිරීමට ජාවා වැඩසටහන

බොළඳ ප්‍රවේශය

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

සංකීර්ණ විශ්ලේෂණය  

කාල සංකීර්ණත්වය වර්ග කළ ලැයිස්තු දෙකක් ඒකාබද්ධ කිරීමට

ඕ (එන් + එම්), එහිදී N සහ M යනු ලැයිස්තු දෙකේ දිග වේ. අපි ප්‍රවේශයන් දෙකටම වරක් ලැයිස්තු දෙකම ගමන් කරන්නෙමු, එබැවින් ඇල්ගොරිතම දෙකම රේඛීය වේ.

මෙයද බලන්න
වලංගු පරිපූර්ණ චතුරස්ර ලීට්කෝඩ් විසඳුම

අභ්‍යවකාශ සංකීර්ණතාව වර්ග කළ ලැයිස්තු දෙකක් ඒකාබද්ධ කිරීමට

ප්‍රශස්ත ප්‍රවේශයේදී, අප පමණක් බව තේරුම් ගැනීම වැදගත්ය දර්ශකයන් හසුරුවන්න. ඉතින්, විචල්යයන් සඳහා නියත අවකාශය මතක භාවිතය සඳහා හේතු වේ. එබැවින් ප්‍රශස්ත ක්‍රමයට අවකාශයේ සංකීර්ණතාවයක් ඇත ඕ (1). ඕ (එන් + එම්) සාකච්ඡා කර ඇති බොළඳ ප්‍රවේශය තුළ අවකාශය භාවිතා වේ.