מיזוג שתי רשימות ממוינות פתרונות ליקוד


רמת קושי קַל
נשאל לעתים קרובות Adobe אמזון בעברית תפוח עץ בלומברג קפיטל אחד פייסבוק Google יבמ מיקרוסופט אורקל
רשימה מקושרת

רשימות מקושרות דומים למערכים בתכונותיהם הליניאריות. אנו יכולים למזג שני מערכים ממוינים כדי ליצור מערך ממוין כולל. בבעיה זו עלינו למזג שתי רשימות מקושרות ממוינות במקום להחזיר רשימה חדשה המכילה אלמנטים משתי הרשימות בצורה ממוינת.

דוגמה

מיזוג שתי רשימות ממוינות פתרונות ליקוד

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
    • temp = ListNode חדש (List1.value) , temp-> הבא = mergeTwoSortedLists (List1-> הבא, List2)
  7. אם List2.value <= List1.value
    • temp = ListNode חדש (List2.value) , temp-> הבא = mergeTwoSortedLists (רשימה 1, רשימה 2 -> הבא)
  8. לחזור טמפ כדי להשיג את הרשימה הרצויה

אלגוריתם (אופטימלי)

  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 הם אורכם של שתי הרשימות. אנו חוצים את שתי הרשימות פעם אחת בשתי הגישות, כך ששני האלגוריתמים הם ליניאריים.

מורכבות בחלל למזג שתי רשימות ממוינות

בגישה האופטימלית, חשוב להבין שאנחנו רק לתפעל את המצביעים. לכן, המרחב הקבוע למשתנים מהווה שימוש בזיכרון. לכן, השיטה האופטימלית מורכבת במרחב O (1). O (N + M) נעשה שימוש במרחב בגישה הנאיבית הנדונה.