दोन क्रमवारीबद्ध याद्या लीटकोड सोल्यूशन्स विलीन करा


अडचण पातळी सोपे
वारंवार विचारले अडोब ऍमेझॉन सफरचंद ब्लूमबर्ग कॅपिटल वन फेसबुक Google IBM मायक्रोसॉफ्ट ओरॅकल
दुवा साधलेली यादी

दुवा साधलेल्या याद्या त्यांच्या रेखीय गुणधर्मांमधील अ‍ॅरेसारखे आहेत. आम्ही एकूण क्रमवारी लावलेले अ‍ॅरे तयार करण्यासाठी दोन सॉर्ट केलेले अ‍ॅरे विलीन करू शकतो. या समस्येमध्ये आम्हाला दोन क्रमवारी लावलेल्या दुव्याच्या सूची विलीन कराव्या लागतील ठिकाणी क्रमवारी लावलेल्या फॅशनमध्ये दोन्ही यादीतील घटक असलेली एक नवीन सूची परत करण्यासाठी.

उदाहरण

दोन क्रमवारीबद्ध याद्या लीटकोड सोल्यूशन्स विलीन करा

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

दृष्टीकोन

हे करण्याचा सर्वात सोपा मार्ग म्हणजे तो वापरणे दोन-सूचक तंत्र नवीन रिक्त यादी तयार करा. दोन्ही पॉइंटरमधील लहान घटक जोडा आणि संबंधित पॉइंटर वाढवा. हा एक चांगला दृष्टिकोन आहे परंतु त्यासाठी जागा वापरणारी अतिरिक्त यादी तयार करणे आवश्यक आहे.

इष्टतम पध्दतीने फक्त करण्यासाठी सतत जागा वापरली पाहिजे ठिकाणी वर्गीकरण. आपण पुनरावृत्ती करण्याच्या पद्धतीचा अवलंब करू शकतो. आमच्याकडे आधीपासूनच दोन्ही याद्यांमध्ये नोड्स संग्रहित आहेत. एक नवीन सूची पॉईंटर आणि त्यानंतरचे “पुढील पॉईंटर्स”ने मेमरीमधील पूर्वनिर्धारित नोड्सकडे निर्देश केले पाहिजे. या प्रक्रियेत आम्ही तयार करतो नाही नवीन नोड्स

अल्गोरिदम (भोळे दृष्टिकोन)

  1. एक फंक्शन तयार करा मर्जटिवोस्टर्डिस्ट () ते अर्ग्युमेंटस म्हणून दोन लिस्ट पॉईंटर घेतात
  2. जर यापैकी कोणतीही एक यादी असेल तर निरर्थक, दुसर्‍याला परत करा
  3. तयार अस्थायी दोन्ही सूचीच्या प्रमुखांमधील लहान नोडला दर्शविणारा चल
  4. कमीतकमी आता, आपल्या निकालावर एक नोड जोडला गेला आहे, म्हणून एक डोके वाढवले ​​पाहिजे
  5. हे एक सबप्रोब्लम तयार करते. तर, त्याच रिकर्सिव्ह फंक्शनला कॉल करा आणि त्यास टेम्पमध्ये जोडा
  6. जर list1.value <list2.value
    • अस्थायी = नवीन यादी नोड (यादी 1. मूल्य) , अस्थायी-> पुढील = मर्ज टूओस्टेडलिस्ट (यादी 1-> पुढील, यादी 2)
  7. जर यादी 2. मूल्य <= यादी 1. मूल्य
    • अस्थायी = नवीन यादी नोड (यादी 2. मूल्य) , अस्थायी-> पुढील = मर्ज टूओस्टेडलिस्ट (यादी 1, यादी 2-> पुढील)
  8. परत अस्थायी इच्छित यादी मिळविण्यासाठी

अल्गोरिदम (इष्टतम)

  1. एक नवीन सूची पॉईंटर तयार करा जे कॉल केले जाईल डमी_हेड.
  2. त्याची देखभाल “कपाळ”(कॉपी पॉईंटर) जेणेकरून आम्ही सूचीत प्रवेश करू शकू डोके पत्ता.
  3. "पुढील पॉईंटर्सच्या डमी_हेडची अशा प्रकारे हाताळणी केली पाहिजे की ते सूचीमधील पूर्वनिर्धारित नोड्सकडे निर्देश करेल l1 आणि l2.
  4. वरील कार्य आम्ही खालील प्रकारे करू शकतोः
    • याद्या त्यांच्या डोक्यापासून सुरू होणा poin्या सूच्यांद्वारे पुनरावृत्ती करा.
    • जोपर्यंत याद्यांपैकी एक पूर्णपणे ट्रॅक केली जात नाही:
      • दोन सूची पॉइंटर्स वरुन लहान मूल्यांचे नोड जोडा डमी_हेड, संबंधित पॉईंटर वाढवित आहे.
    • आता, पॉईंटर्सपैकी किमान एक आहे निरर्थक. तर, जोडा शून्य बनावट डोके यादी.
  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). ओ (एन + एम) चर्चेत असलेल्या भोळ्या दृष्टिकोनातून जागा वापरली जाते.