צונויפגיסן צוויי סאָרטעד ליס לעעטקאָדע סאַלושאַנז


שוועריקייט לעוועל גרינג
אָפט געבעטן אין אַדאָובי אַמאַזאָן עפּל בלומבערג Capital One facebook גוגל יבם מייקראָסאָפֿט אָראַקל
לינקעד-רשימה

לינקעד רשימות זענען פּונקט ווי ערייז אין זייער לינעאַר פּראָפּערטיעס. מיר קענען צונויפגיסן צוויי סאָרטעד ערייז צו פאָרעם אַ קוילעלדיק סאָרטעד מענגע. אין דעם פּראָבלעם, מיר האָבן צונויפגיסן צוויי סאָרטיד לינגקט רשימות אין פּלאַץ צו צוריקקומען אַ נייַע רשימה וואָס כּולל עלעמענטן פון ביידע רשימות אויף אַ סאָרטעד וועג.

בייַשפּיל

צונויפגיסן צוויי סאָרטעד ליס לעעטקאָדע סאַלושאַנז

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

צוגאַנג

די סימפּלאַסט וועג צו טאָן דאָס איז ניצן די צוויי-טייַטל טעכניק. שאַפֿן אַ נייַ ליידיק רשימה. לייג די קלענערער עלעמענטן צווישן די פּוינטערז און ינקראַמאַנט די קאָראַספּאַנדינג טייַטל. דאָס איז אַ גוטע צוגאַנג אָבער ריקווייערז אַ נייַע רשימה וואָס קאַנסומז פּלאַץ.

די אָפּטימאַל צוגאַנג זאָל פאַרנוצן קעסיידערדיק פּלאַץ בלויז צו מאַכן אַ אין פּלאַץ סאָרטינג. מיר קענען נאָכפאָלגן די יטעראַטיווע צוגאַנג. מיר האָבן שוין די נאָדעס סטאָרד אין ביידע רשימות. שאַפֿן אַ נייַע רשימה טייַטל און די סאַבסאַקוואַנט "ווייַטער פּוינטערז”זאָל פונט צו פּרעדעפינעד נאָודז אין די זכּרון. אין דעם פּראָצעס, מיר מאַכן קיין נייַ נאָודז.

אַלגערידאַם (נאַיוו צוגאַנג)

  1. שאַפֿן אַ פֿונקציע mergeTwoSortedLists () אַז נעמט צוויי רשימה פּוינטערז ווי טענות
  2. אויב איינער פון די רשימות איז נול, צוריקקומען די אנדערע איינער
  3. שאַפֿן אַ טעמפּ בייַטעוודיק וואָס וועט ווייַזן צו דער קלענערער נאָדע צווישן קעפ פון ביידע רשימות
  4. איצט, אין מינדסטער, איין נאָדע איז אַפּפּענדעד צו אונדזער רעזולטאַט, אַזוי איין קאָפּ זאָל זיין ינקראַמענטיד
  5. דאָס קריייץ אַ סאַב-פּראָבלעם. אַזוי, רופן די זעלבע רעקורסיווע פונקציע און צולייגן עס צו טעמפּ
  6. אויב ליסט 1. ווערט <ליסטע 2. ווערט
    • טעמפּ = נייַע ListNode (List1.value) , טעמפּ-> ווייַטער = mergeTwoSortedLists (ליסט 1 -> ווייַטער, ליסט 2)
  7. אויב List2.value <= List1.value
    • טעמפּ = נייַע ListNode (List2.value) , טעמפּ-> ווייַטער = mergeTwoSortedLists (ליסט 1, ליסט 2 -> ווייַטער)
  8. צוריקקומען טעמפּ צו באַקומען די געבעטן רשימה

אַלגערידאַם (אָפּטימאַל)

  1. שאַפֿן אַ נייַ רשימה טייַטל וואָס וועט זיין גערופֿן dummy_head.
  2. טייַנען זייַן “פּרעהעאַד”(קאָפּיע טייַטל) אַזוי אַז מיר קענען אַקסעס די רשימה קאָפּ אַדרעס.
  3. די "ווייַטער פּוינטערז”פון dummy_head זאָל זיין מאַניפּיאַלייטיד אַזוי אַז עס ווייזט צו די פּרעדעפיינד נאָודז אין רשימות l1 און l2.
  4. מיר קענען טאָן די אויבן אַרבעט אויף די פאלגענדע וועגן:
    • האַלטן די יטעראַטינג די רשימות מיט פּוינטערז סטאַרטינג פֿון זייער קעפ.
    • סיידן איינער פון די רשימות איז גאָר דורכגעקאָכט:
      • צוגעבן די קלענערער וואַליוד נאָדע פֿון די צוויי רשימה פּוינטערז צו די dummy_head, ינקרעמענטינג די קאָראַספּאַנדינג טייַטל.
    • איצט, לפּחות איינער פון די פּוינטערז איז נול. אַזוי, צוגעבן די ניט-נאַל רשימה צו די באָק קאָפּ.
  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

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי צו צונויפגיסן צוויי אויסגעשטעלט רשימות

אָ (N + M), ווו N און M זענען די לענגקטס פון די צוויי רשימות. מיר דורכגיין ביידע רשימות אַמאָל אין ביידע אַפּראָוטשיז, אַזוי ביידע אַלגערידאַמז זענען לינעאַר.

ספעיס קאַמפּלעקסיטי צו צונויפגיסן צוויי אויסגעשטעלט רשימות

אין דער אָפּטימאַל צוגאַנג, עס איז וויכטיק צו פֿאַרשטיין אַז מיר נאָר מאַניפּולירן די פּוינטערז. דער קעסיידערדיק פּלאַץ פֿאַר וועריאַבאַלז אַקאַונץ פֿאַר זכּרון באַניץ. דעריבער, דער אָפּטימאַל אופֿן האט אַ פּלאַץ קאַמפּלעקסיטי פון אָ (1). אָ (N + M) אָרט איז געניצט אין דעם נאַיוו צוגאַנג דיסקאַסט.