Leetcode шешімдерінің екі сұрыпталған тізімін біріктіру  


Күрделілік дәрежесі оңай
Жиі кіреді Adobe Amazon алма Bloomberg Capital One Facebook Google IBM Microsoft Oracle
алгоритмдер кодтау сұхбат сұхбат дайындау LeetCode LeetCodeSolutions Байланыстырылған тізім

Байланыстырылған тізімдер сызықтық қасиеттері бойынша массивтерге өте ұқсас. Біз екі сұрыпталған массивті біріктіріп, жалпы сұрыпталған массив құра аламыз. Бұл мәселеде біз екі сұрыпталған тізімді біріктіруіміз керек орында екі тізімнің элементтерін сұрыпталған түрде қамтитын жаңа тізімді қайтару.

мысал  

Leetcode шешімдерінің екі сұрыпталған тізімін біріктіру

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

жақындау  

Мұны жасаудың қарапайым тәсілі екі көрсеткіш техника. Жаңа бос тізім жасаңыз. Екі көрсеткіштің арасына кіші элементтерді қосып, сәйкес көрсеткішті үлкейтіңіз. Бұл жақсы тәсіл, бірақ кеңістікті тұтынатын қосымша тізім жасауды талап етеді.

Оңтайлы тәсіл тек қана орындау үшін тұрақты кеңістікті тұтынуы керек орында сұрыптау. Итеративті тәсілді ұстануға болады. Бізде екі тізімде де сақталған түйіндер бар. Жаңа тізім көрсеткішін жасаңыз және одан кейінгі «келесі көрсеткіштер»Жадындағы алдын-ала анықталған түйіндерді көрсетуі керек. Бұл процесте біз жасаймыз жоқ жаңа түйіндер.

Алгоритм (аңғалдық тәсіл)  

  1. Функцияны жасаңыз mergeTwoSortedLists () бұл аргумент ретінде екі тізім көрсеткіштерін алады
  2. Егер тізімдердің біреуі болса ЖОҚ, екіншісін қайтарыңыз
  3. а жасау temp екі тізімнің басындағы кіші түйінді көрсететін айнымалы
  4. Енді, кем дегенде, біздің нәтижеге бір түйін қосылады, сондықтан бір бас өсуі керек
  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. қайтару temp қажетті тізімді алу үшін
Сондай-ақ, қараңыз
Интерактивті шешім кодын енгізу

Алгоритм (оңтайлы)  

  1. Шақырылатын жаңа тізім көрсеткішін жасаңыз лақап_бас.
  2. Оның «сақталуыбас»(Нұсқауды көшіру), біз тізімге қол жеткізе аламыз бас мекен-жайы.
  3. «келесі көрсеткіштерDummy_head-ді тізімдердегі алдын-ала анықталған түйіндерге нұсқайтындай етіп жасау керек l1 және l2.
  4. Жоғарыдағы тапсырманы келесі тәсілдермен орындай аламыз:
    • Тізімдерді басынан бастап көрсеткіштермен қайталай беріңіз.
    • Егер тізімдердің біреуі толығымен өтпесе:
      • Тізімнің екі көрсеткішінен кіші мәнді түйінді қосыңыз маникюр_бас, сәйкес көрсеткішті ұлғайту.
    • Енді көрсеткіштердің кем дегенде біреуі ЖОҚ. Сонымен, қосыңыз нөлдік емес лақап басына тізім.
  5. Қайтару бас лақап тізімінің.

Іске асыру  

Екі сұрыпталған тізімді біріктіруге арналған C ++ бағдарламасы

Аңғал көзқарас

#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

Екі сұрыпталған тізімді біріктіруге арналған Java бағдарламасы

Аңғал көзқарас

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 екі тізімнің ұзындықтары. Біз екі тәсілде де екі тізімді бір рет айналып өтеміз, сондықтан екі алгоритм де сызықтық болып табылады.

Сондай-ақ, қараңыз
Leitcode квадратының дұрыс шешімі

Ғарыштың күрделілігі екі сұрыпталған тізімді біріктіру үшін

Оңтайлы тәсілде біз тек екенімізді түсіну маңызды көрсеткіштермен манипуляциялау. Сонымен, айнымалылардың тұрақты кеңістігі жадыны пайдалануды ескереді. Сондықтан оңтайлы әдіс кеңістіктің күрделілігіне ие O (1). O (N + M) кеңістік талқыланған аңғалдық тәсілде қолданылады.