రెండు క్రమబద్ధీకరించిన జాబితాలు లీట్‌కోడ్ పరిష్కారాలను విలీనం చేయండి


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది Adobe అమెజాన్ ఆపిల్ బ్లూమ్బెర్గ్ కాపిటల్ వన్ <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> గూగుల్ IBM మైక్రోసాఫ్ట్ ఒరాకిల్
లింక్డ్-జాబితా

లింక్ చేసిన జాబితాలు వాటి సరళ లక్షణాలలో శ్రేణుల వలె ఉంటాయి. మొత్తం క్రమబద్ధీకరించిన శ్రేణిని రూపొందించడానికి మేము రెండు క్రమబద్ధీకరించిన శ్రేణులను విలీనం చేయవచ్చు. ఈ సమస్యలో, మేము రెండు క్రమబద్ధీకరించిన లింక్ జాబితాలను విలీనం చేయాలి స్థానంలో క్రమబద్ధీకరించిన పద్ధతిలో రెండు జాబితాల అంశాలను కలిగి ఉన్న క్రొత్త జాబితాను తిరిగి ఇవ్వడానికి.

ఉదాహరణ

రెండు క్రమబద్ధీకరించిన జాబితాలు లీట్‌కోడ్ పరిష్కారాలను విలీనం చేయండి

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

అప్రోచ్

దీన్ని చేయడానికి సులభమైన మార్గం రెండు-పాయింటర్ టెక్నిక్. క్రొత్త ఖాళీ జాబితాను సృష్టించండి. రెండు పాయింటర్లలో చిన్న అంశాలను జోడించి, సంబంధిత పాయింటర్‌ను పెంచండి. ఇది మంచి విధానం కాని స్థలాన్ని వినియోగించే అదనపు జాబితాను సృష్టించడం అవసరం.

ఆప్టిమల్ అప్రోచ్ ఒక స్థిరమైన స్థలాన్ని మాత్రమే వినియోగించుకోవాలి స్థానంలో సార్టింగ్. మేము పునరుక్తి విధానాన్ని అనుసరించవచ్చు. మేము ఇప్పటికే రెండు జాబితాలలో నోడ్స్ నిల్వ చేసాము. క్రొత్త జాబితా పాయింటర్‌ను సృష్టించండి మరియు దాని తదుపరి “తదుపరి పాయింటర్లు”మెమరీలో ముందే నిర్వచించిన నోడ్‌లకు సూచించాలి. ఈ ప్రక్రియలో, మేము సృష్టిస్తాము క్రొత్త నోడ్లు.

అల్గోరిథం (అమాయక విధానం)

  1. ఒక ఫంక్షన్ సృష్టించండి mergeTwoSortedLists () ఇది రెండు జాబితా పాయింటర్లను వాదనలుగా తీసుకుంటుంది
  2. జాబితాలలో ఒకటి ఉంటే శూన్య మరొకటి తిరిగి ఇవ్వండి
  3. ఒక సృష్టించు తాత్కాలిక రెండు జాబితాల తలలలో చిన్న నోడ్‌కు సూచించే వేరియబుల్
  4. ఇప్పుడు, కనీసం, మా ఫలితానికి ఒక నోడ్ జోడించబడింది, కాబట్టి ఒక తల పెంచాలి
  5. ఇది ఉపప్రాబ్లమ్‌ను సృష్టిస్తుంది. కాబట్టి, అదే పునరావృత ఫంక్షన్‌కు కాల్ చేసి, దానిని తాత్కాలికంగా చేర్చండి
  6. List1.value <List2.value అయితే
    • టెంప్ = క్రొత్త జాబితా నోడ్ (List1.value) , temp-> next = mergeTwoSortedLists (List1-> తదుపరి, List2)
  7. List2.value <= List1.value అయితే
    • టెంప్ = క్రొత్త జాబితా నోడ్ (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

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత రెండు క్రమబద్ధీకరించిన జాబితాలను విలీనం చేయడానికి

O (N + M), (ఇక్కడ N మరియు M రెండు జాబితాల పొడవు. మేము రెండు విధానాలలో ఒకసారి రెండు జాబితాలను దాటుతాము, కాబట్టి రెండు అల్గోరిథంలు సరళంగా ఉంటాయి.

అంతరిక్ష సంక్లిష్టత రెండు క్రమబద్ధీకరించిన జాబితాలను విలీనం చేయడానికి

ఆప్టిమల్ విధానంలో, మనం మాత్రమే అర్థం చేసుకోవాలి పాయింటర్లను మార్చండి. కాబట్టి, వేరియబుల్స్ కోసం స్థిరమైన స్థలం మెమరీ వినియోగానికి కారణమవుతుంది. అందువల్ల, సరైన పద్ధతి యొక్క స్థలం సంక్లిష్టతను కలిగి ఉంటుంది O (1). O (N + M) చర్చించిన అమాయక విధానంలో స్థలం ఉపయోగించబడుతుంది.