ادغام دو لیست مرتب شده Leetcode Solutions  


سطح دشواری ساده
اغلب در خشت آمازون سیب بلومبرگ یکی از سرمایه فیس بوک گوگل آی بی ام مایکروسافت وحی
الگوریتم برنامه نویسی مصاحبه مصاحبه آماده LeetCode LeetCodeSolutions لینک شده

لیست های پیوند داده شده از نظر خصوصیات خطی کاملاً شبیه آرایه ها هستند. ما می توانیم دو آرایه مرتب شده را با هم ادغام کنیم و یک آرایه مرتب شده را تشکیل دهیم. در این مشکل ، ما باید دو لیست پیوندی مرتب شده را ادغام کنیم درجا برای بازگشت به لیست جدیدی که شامل عناصر هر دو لیست به صورت طبقه بندی شده است.

مثال  

ادغام دو لیست مرتب شده Leetcode Solutionsسنجاق

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 جدید (فهرست 1. مقدار) ، دما-> بعدی = mergeTwoSortedLists (List1-> next، List2)
  7. اگر List2.value <= List1.value
    • دما = ListNode جدید (فهرست 2. مقدار) ، دما-> بعدی = mergeTwoSortedLists (List1، List2-> next)
  8. برگشت دما تا لیست مورد نظر را بدست آورید
همچنین مشاهده کنید
محلول Leetcode Interval را وارد کنید

الگوریتم (بهینه)  

  1. یک اشاره گر لیست جدید ایجاد کنید که فراخوانی شود سر ساختگی
  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

برنامه جاوا برای ادغام دو لیست مرتب شده

رویکرد ساده لوحانه

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 طول دو لیست هستند. ما هر دو لیست را یک بار در هر دو رویکرد مرور می کنیم ، بنابراین هر دو الگوریتم خطی هستند.

همچنین مشاهده کنید
راه حل معتبر Perfect Square Leetcode

پیچیدگی فضا برای ادغام دو لیست مرتب شده

در رویکرد بهینه ، مهم است که درک کنیم فقط ما هستیم اشاره گرها را دستکاری کنید. بنابراین ، فضای ثابت متغیرها مربوط به میزان استفاده از حافظه است. بنابراین ، روش بهینه دارای پیچیدگی فضایی است O (1). O (N + M) فضا در رویکرد ساده لوحی مورد بحث استفاده می شود.