دمج حلول Leetcode لقائمتين تم فرزهما  


مستوى الصعوبة سهل
كثيرا ما يطلب في أدوبي أمازون أجهزة آبل بلومبرغ عاصمة واحدة Facebook جوجل IBM Microsoft أوراكل
خوارزميات الترميز المقابلة الشخصية مقابلة LeetCode LeetCodeSolutions قائمة مرتبطة

القوائم المرتبطة تشبه المصفوفات تمامًا في خصائصها الخطية. يمكننا دمج مصفوفتين مفروزتين لتكوين مصفوفة مرتبة بشكل عام. في هذه المشكلة ، يتعين علينا دمج قائمتين مرتبطتين تم فرزهما في المكان لإرجاع قائمة جديدة تحتوي على عناصر كلتا القائمتين بطريقة مرتبة.

مثال  

دمج حلول Leetcode لقائمتين تم فرزهما

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

الرسالة  

إن أبسط طريقة للقيام بذلك هي استخدام امتداد مؤشرين تقنية. قم بإنشاء قائمة فارغة جديدة. قم بإلحاق العناصر الأصغر بين كل من المؤشرات وقم بزيادة المؤشر المقابل. هذا أسلوب جيد ولكنه يتطلب إنشاء قائمة إضافية تستهلك مساحة.

يجب أن يستهلك النهج الأمثل مساحة ثابتة فقط من أجل القيام بـ في المكان فرز. يمكننا اتباع النهج التكراري. لدينا بالفعل العقد المخزنة في كلتا القائمتين. قم بإنشاء مؤشر قائمة جديد و "المؤشرات التالية"يجب أن يشير إلى العقد المحددة مسبقًا في الذاكرة. في هذه العملية ، نخلق لا عقد جديدة.

الخوارزمية (نهج ساذج)  

  1. قم بإنشاء وظيفة mergeTwoSortedLists () يأخذ مؤشري القائمة كوسيطتين
  2. إذا كانت أي من القائمتين NULL، إعادة الآخر
  3. إنشاء درجة الحرارة المتغير الذي سيشير إلى العقدة الأصغر بين رؤوس كلتا القائمتين
  4. الآن ، على الأقل ، تم إلحاق عقدة واحدة بنتائجنا ، لذلك يجب زيادة رأس واحدة
  5. هذا يخلق مشكلة فرعية. لذلك ، قم باستدعاء نفس الوظيفة العودية وإلحاقها مؤقتًا
  6. إذا كانت List1.value <List2.value
    • درجة الحرارة = ListNode الجديد (List1.value) ، درجة الحرارة> التالي = mergeTwoSortedLists (List1-> next ، List2)
  7. إذا كانت List2.value <= List1.value
    • درجة الحرارة = ListNode الجديد (List2.value) ، درجة الحرارة> التالي = mergeTwoSortedLists (List1 ، List2-> next)
  8. الإرجاع درجة الحرارة للحصول على القائمة المطلوبة
انظر أيضا
أدخل حل Leetcode الفاصل

الخوارزمية (الأمثل)  

  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

تحليل التعقيد  

تعقيد الوقت لدمج قائمتين تم فرزهما

O (N + M) ، أين N و M هي أطوال القائمتين. نجتاز كلتا القائمتين مرة واحدة في كلا الطريقتين ، لذا فإن كلا الخوارزميات خطية.

انظر أيضا
محلول Leetcode مربع مثالي صالح

تعقيد الفضاء لدمج قائمتين تم فرزهما

في النهج الأمثل ، من المهم أن نفهم أننا فقط التلاعب بالمؤشرات. لذلك ، فإن المساحة الثابتة للمتغيرات تمثل استخدام الذاكرة. لذلك ، فإن الطريقة المثلى لها تعقيد مساحة يا (1). يا (N + M) يتم استخدام الفضاء في النهج الساذج الذي تمت مناقشته.