Споји две сортиране листе Леетцоде решења


Ниво тешкоће Лако
Често питани у адобе амазонка јабука Блоомберг Цапитал Оне фацебоок гоогле ИБМ- мицрософт пророчанство
Повезана листа

Повезане листе су по својим линеарним својствима сасвим попут низова. Можемо спојити два сортирана низа да бисмо формирали целокупни сортирани низ. У овом проблему морамо спојити две сортиране повезане листе на месту за враћање нове листе која на сортирани начин садржи елементе обе листе.

Пример

Споји две сортиране листе Леетцоде решења

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

Приступ

Најједноставнији начин за то био би коришћење двострука техника. Направите нову празну листу. Додајте мање елементе међу оба показивача и повећајте одговарајући показивач. Ово је добар приступ, али захтева стварање додатне листе која троши простор.

Оптимални приступ треба да заузима константан простор само да би се направио на месту сортирање. Можемо следити итеративни приступ. Чворови већ имамо ускладиштене на обе листе. Направите нови показивач листе и његове наредне “следећи показивачи”Треба да упућује на унапред дефинисане чворове у меморији. У овом процесу ми стварамо не нови чворови.

Алгоритам (наивни приступ)

  1. Направите функцију мергеТвоСортедЛистс () то узима два показивача на списак као аргументе
  2. Ако је било који од списка НУЛА, врати другу
  3. Креирање Температура променљива која ће указивати на мањи чвор међу главама обе листе
  4. Сада је барем један чвор додан нашем резултату, па би требало повећати једну главу
  5. Ово ствара подпроблем. Дакле, позовите исту рекурзивну функцију и додајте је темп
  6. Ако је Лист1.валуе <Лист2.валуе
    • темп = нови ЛистНоде (Лист1.валуе) , темп-> нект = мергеТвоСортедЛистс (Листа1-> следећа, Листа2)
  7. Ако је Лист2.валуе <= Лист1.валуе
    • темп = нови ЛистНоде (Лист2.валуе) , темп-> нект = мергеТвоСортедЛистс (Лист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). О (Н + М) простор се користи у наивном приступу о коме се говори.