இரண்டு வரிசைப்படுத்தப்பட்ட பட்டியல்களை லீட்கோட் தீர்வுகளை ஒன்றிணைக்கவும்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அடோப் அமேசான் ஆப்பிள் ப்ளூம்பெர்க் மூலதன ஒன்று பேஸ்புக் கூகிள் ஐபிஎம் மைக்ரோசாப்ட் ஆரக்கிள்
இணைக்கப்பட்ட பட்டியல்

இணைக்கப்பட்ட பட்டியல்கள் அவற்றின் நேரியல் பண்புகளில் வரிசைகள் போன்றவை. ஒட்டுமொத்த வரிசைப்படுத்தப்பட்ட வரிசையை உருவாக்க நாம் இரண்டு வரிசைப்படுத்தப்பட்ட வரிசைகளை ஒன்றிணைக்கலாம். இந்த சிக்கலில், வரிசைப்படுத்தப்பட்ட இணைக்கப்பட்ட இரண்டு பட்டியல்களை நாம் ஒன்றிணைக்க வேண்டும் இடத்தில் வரிசைப்படுத்தப்பட்ட பாணியில் இரு பட்டியல்களின் கூறுகளையும் கொண்ட புதிய பட்டியலைத் தர.

உதாரணமாக

இரண்டு வரிசைப்படுத்தப்பட்ட பட்டியல்களை லீட்கோட் தீர்வுகளை ஒன்றிணைக்கவும்

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 என்றால்
    • வெப்பநிலை = புதிய பட்டியல் முனை (பட்டியல் 1. மதிப்பு) , temp-> next = mergeTwoSortedLists (பட்டியல் 1-> அடுத்து, பட்டியல் 2)
  7. List2.value <= List1.value என்றால்
    • வெப்பநிலை = புதிய பட்டியல் முனை (பட்டியல் 2. மதிப்பு) , temp-> next = mergeTwoSortedLists (பட்டியல் 1, பட்டியல் 2-> அடுத்தது)
  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). O (N + M) விவாதிக்கப்பட்ட அப்பாவி அணுகுமுறையில் இடம் பயன்படுத்தப்படுகிறது.