Միաձուլեք երկու տեսակավորված ցուցակներ Leetcode լուծումները


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Adobe Amazon խնձոր Bloomberg Capital One facebook Google IBM Microsoft Պատգամախոս
Կապված ցուցակ

Կապված ցուցակներ իրենց գծային հատկություններով բավականին նման են զանգվածների: Կարող ենք միավորել երկու տեսակավորված զանգված `ընդհանուր տեսակավորված զանգված կազմելու համար: Այս խնդրում մենք պետք է միավորենք երկու տեսակավորված կապակցված ցուցակներ տեղում վերադարձնել նոր ցուցակ, որը դասավորված է երկու ցուցակների էլեմենտները:

Օրինակ

Միաձուլեք երկու տեսակավորված ցուցակներ Leetcode լուծումները

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
    • տեմպ = նոր ListNode (List1.value) , տեմպ-> հաջորդ = mergeTwoSortedLists (Listուցակ 1-> հաջորդ, 2ուցակ XNUMX)
  7. Եթե ​​List2.value <= List1.value
    • տեմպ = նոր ListNode (List2.value) , տեմպ-> հաջորդ = mergeTwoSortedLists (Listուցակ 1, 2ուցակ XNUMX-> հաջորդ)
  8. Վերադառնալ Ջերմ ցանկալի ցուցակ ստանալու համար

Ալգորիթմ (օպտիմալ)

  1. Ստեղծեք ցուցակի նոր ցուցիչ, որը կկոչվի կեղծ-գլուխ:
  2. Պահպանել իր «նախածանց”(Պատճենել ցուցիչը), որպեսզի կարողանանք մուտք գործել ցուցակ գլխավոր հասցեով:
  3. The "հաջորդ ցուցիչները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

Բարդության վերլուծություն

Timeամանակի բարդություն միավորել երկու տեսակավորված ցուցակները

O (N + M), որտեղ N և M երկու ցուցակների երկարություններն են: Երկու ցուցակներն էլ մենք անցնում ենք միանգամից և՛ երկու մոտեցումներում, այնպես որ երկու ալգորիթմներն էլ գծային են:

Տիեզերական բարդություն միավորել երկու տեսակավորված ցուցակները

Օպտիմալ մոտեցման մեջ կարևոր է հասկանալ, որ միայն մենք ենք շահարկել ցուցիչները, Այսպիսով, փոփոխականների համար անընդհատ տարածությունը հաշվի է առնում հիշողության օգտագործումը: Հետեւաբար, օպտիմալ մեթոդը տիեզերական բարդություն ունի Ո (1). O (N + M) տարածությունը օգտագործվում է քննարկվող միամիտ մոտեցման մեջ: