দুটি সাজানো তালিকাগুলি লেটকোড সমাধানগুলিকে মার্জ করুন


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় রৌদ্রপক্ব ইষ্টক মর্দানী স্ত্রীলোক আপেল ব্লুমবার্গ ক্যাপিটাল ওয়ান ফেসবুক গুগল আইবিএম মাইক্রোসফট আকাশবাণী
যোজিত তালিকা

লিঙ্কযুক্ত তালিকাগুলি তাদের লিনিয়ার বৈশিষ্ট্যগুলিতে অ্যারেগুলির মতো বেশ। সামগ্রিকভাবে বাছাই করা অ্যারে গঠনে আমরা দুটি বাছাই করা অ্যারে মার্জ করতে পারি। এই সমস্যায়, আমাদের দুটি বাছাইযুক্ত লিঙ্কযুক্ত তালিকার একত্রীকরণ করতে হবে জায়গায় একটি নতুন তালিকাতে ফিরিয়ে আনতে যাতে সাজানো ফ্যাশনে উভয় তালিকার উপাদান রয়েছে।

উদাহরণ

দুটি সাজানো তালিকাগুলি লেটকোড সমাধানগুলিকে মার্জ করুন

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

অভিগমন

এটি করার সহজ উপায় হ'ল এটি ব্যবহার করা দ্বি-পয়েন্টার প্রযুক্তি. একটি নতুন খালি তালিকা তৈরি করুন। উভয় পয়েন্টার মধ্যে ছোট উপাদান সংযোজন এবং সংশ্লিষ্ট পয়েন্টার বৃদ্ধি। এটি একটি ভাল পদ্ধতির তবে জায়গা খায় এমন অতিরিক্ত তালিকা তৈরি করা দরকার।

সর্বোত্তম পদ্ধতির শুধুমাত্র একটি করার জন্য ধ্রুবক স্থান গ্রহণ করা উচিত জায়গায় শ্রেণীবিভাজন. আমরা পুনরাবৃত্তি পদ্ধতির অনুসরণ করতে পারি। আমরা ইতিমধ্যে দুটি তালিকায় নোড সংরক্ষণ করেছি। একটি নতুন তালিকা পয়েন্টার এবং তার পরবর্তী "তৈরি করুনপরবর্তী পয়েন্টার"স্মৃতিতে পূর্বনির্ধারিত নোডগুলিকে নির্দেশ করা উচিত। এই প্রক্রিয়াতে, আমরা তৈরি না। নতুন নোড

অ্যালগরিদম (নিষ্পাপ দৃষ্টিভঙ্গি)

  1. একটি ফাংশন তৈরি করুন মার্জটুইসোর্টড লিস্টস () এটি আর্গুমেন্ট হিসাবে দুটি তালিকা পয়েন্টার লাগে
  2. তালিকাগুলির মধ্যে যদি হয় খালি, অন্যটি ফিরিয়ে দাও
  3. একটা তৈরি কর টেম্প ভেরিয়েবল যা উভয় তালিকার শীর্ষের মধ্যে ছোট নোডকে নির্দেশ করবে
  4. এখন, কমপক্ষে একটি ফলাফল আমাদের ফলাফলের সাথে সংযুক্ত করা হয়েছে, সুতরাং একটি মাথা বাড়ানো উচিত should
  5. এটি একটি উপ-সমস্যা তৈরি করে। সুতরাং, একই পুনরাবৃত্তির ফাংশনটি কল করুন এবং এটি টেম্পারে সংযুক্ত করুন
  6. যদি list1.value <List2.value
    • অস্থায়ী = নতুন তালিকানোড (তালিকা 1. মূল্য) , অস্থায়ী-> পরবর্তী = = মার্জটুইসওয়ার্ডলিস্টস (তালিকা 1-> পরবর্তী, তালিকা 2)
  7. যদি list2.value <= list1.value
    • অস্থায়ী = নতুন তালিকানোড (তালিকা 2. মূল্য) , অস্থায়ী-> পরবর্তী = = মার্জটাইজসোর্টস তালিকাগুলি (তালিকা 1, তালিকা 2-> পরবর্তী)
  8. প্রত্যাবর্তন টেম্প পছন্দসই তালিকা পেতে

অ্যালগরিদম (অনুকূল)

  1. একটি নতুন তালিকা পয়েন্টার তৈরি করুন যা বলা হবে ডামি_হেড
  2. এটি বজায় রাখুন “কপাল”(কপি পয়েন্টার) যাতে আমরা তালিকাটি অ্যাক্সেস করতে পারি মাথা ঠিকানা।
  3. দ্য "পরবর্তী পয়েন্টার"ডামি_হেডকে এমনভাবে চালিত করা উচিত যাতে এটি তালিকায় পূর্বনির্ধারিত নোডগুলিকে নির্দেশ করে l1 এবং l2.
  4. উপরের কাজটি আমরা নিম্নলিখিত উপায়ে করতে পারি:
    • পয়েন্টারগুলি দিয়ে তাদের মাথা থেকে শুরু করে তালিকাগুলি পুনরাবৃত্তি করুন।
    • তালিকার একটি সম্পূর্ণরূপে বিপরীত না হলে:
      • দুটি তালিকার পয়েন্টার থেকে ছোট মূল্যবান নোড যুক্ত করুন ডামি_হেড, সংশ্লিষ্ট পয়েন্টার বৃদ্ধি।
    • এখন, পয়েন্টারগুলির মধ্যে কমপক্ষে একটি খালি. সুতরাং, সংযোজন নন-নাল ডামি মাথা তালিকা।
  5. ফেরত দিন মাথা ডামি তালিকার।

বাস্তবায়ন

সি ++ প্রোগ্রাম দুটি সাজানো তালিকাগুলি মার্জ করার জন্য

নিষ্পাপ দৃষ্টিভঙ্গি

#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

জটিলতা বিশ্লেষণ

সময় জটিলতা দুটি সাজানো তালিকার মার্জ করতে

ও (এন + এম), কোথায় N এবং M দুটি তালিকার দৈর্ঘ্য। আমরা উভয় পদ্ধতির একবারে উভয় তালিকাকে অতিক্রম করি, সুতরাং উভয়ই অ্যালগরিদম লিনিয়ার।

স্পেস জটিলতা ity দুটি সাজানো তালিকার মার্জ করতে

সর্বোত্তম পদ্ধতির মধ্যে, এটি কেবল আমাদের তা বোঝা গুরুত্বপূর্ণ পয়েন্টারগুলি পরিচালনা। সুতরাং, ভেরিয়েবলের ধ্রুবক স্পেস মেমোরি ব্যবহারের জন্য অ্যাকাউন্ট করে। অতএব, অনুকূল পদ্ধতির একটি স্পেস জটিলতা রয়েছে ও (1). ও (এন + এম) আলোচিত নিষ্পাপ দৃষ্টিভঙ্গিতে স্থান ব্যবহার করা হয়।