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


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

এই সমস্যার লক্ষ্য হ'ল প্রদত্ত নোডগুলিকে অদলবদল করা যোজিত তালিকা জোড়ায়, অর্থাত্, প্রতিটি দুটি সংলগ্ন নোড অদলবদল করা। যদি আমাদের তালিকা নোডের মানটি অদলবদল করার অনুমতি দেওয়া হয় তবে সমস্যাটি তুচ্ছ। সুতরাং, আমাদের নোডের মানগুলি সংশোধন করার অনুমতি নেই।

উদাহরণ

1 2 3 4
2 1 4 3
6 7 3
7 6 3

অভিগমন

আমরা লক্ষ করতে পারি যে আমরা একটি জোড়ায় দুটি নোড অদলবদল করতে পারি। এখানে অদলবদলটির অর্থ পয়েন্টারগুলি এমনভাবে পরিচালনা করা যাতে প্রথম নোডটি লিঙ্কযুক্ত তালিকার বাকি অংশের সাথে সংযুক্ত থাকে এবং দ্বিতীয় নোড এখন হয়ে যায় মাথা প্রথম নোডের দিকে নির্দেশ করছে।

লেটকোড সমাধানগুলিতে একটি তালিকার নোড অদলবদল করুন

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

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

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

  1. সাধারণ বেস শর্তগুলি এমন হয় যখন একটি জোড় গঠনের জন্য দুটি নোডও থাকে না। এই ক্ষেত্রে:
    • তালিকা হতে পারে শূন্য অথবা একটি আইটেম থাকতে পারে।
    • এটি হিসাবে এটি ফেরত দিন।
  2. এখন যে আমাদের একটি জুড়ি আছে, ব্যবহার করুন প্রথম এবং দ্বিতীয় আমাদের জোড়া প্রথম এবং দ্বিতীয় আইটেম বোঝাতে।
  3. যেহেতু প্রথম নোড এখন এই জুটির লেজ হয়ে উঠবে,
    1. পরবর্তী জোড় থেকে শুরু করে পুনরাবৃত্ত ফাংশন কল করুন (নোড পরে) after দ্বিতীয়).
    2. সাবপ্রব্লেমটি ফাংশনটির মাধ্যমে সমাধান করা হয় এবং এতে সংযোজন করা হয় প্রথম নোড
    3. এখন, যোগ করুন প্রথম নোড, যা এছাড়াও আছে বিশ্রাম এটির সাথে সংযুক্ত তালিকার দ্বিতীয় নোডে।
  4. যেহেতু আমরা চাই দ্বিতীয় নোড সঙ্গে অদলবদল করা প্রথম সেকেন্ড এখন মাথা হয়ে যাবে,
    1. প্রত্যাবর্তন দ্বিতীয়।

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

  1. একটা তৈরি কর আগে পয়েন্টারটি কিছু ডামি নোডের দিকে নির্দেশ করে এটি বজায় রাখে কপাল.
  2. সেট পরবর্তী তালিকার বর্তমান প্রধান হিসাবে আগের নোডের।
  3. এই পূর্ববর্তী পয়েন্টারটি পরবর্তী অদলবদল জোড়াটিকে নির্দেশ করতে পারে।
  4. তালিকা থাকলে শূন্য বা শুধুমাত্র একটি উপাদান আছে
    • তালিকাটি ফিরিয়ে দিন
  5. তালিকার অবসান ঘটে বা কেবল একটি নোড বাকি আছে এমন একটি পয়েন্টে পৌঁছা পর্যন্ত পুনরাবৃত্তি করুন:
    • পরবর্তী জোড়ার ঠিকানাটি একটিতে সংরক্ষণ করুন টেম্প পরিবর্তনশীল।
    • এই জোড়ায় দুটি নোড অদলবদল করুন: প্রথম নোড এবং দ্বিতীয় নোড
    • এই জোড়ের দ্বিতীয় নোডের সাথে অ্যাডভনডটি সংযুক্ত করুন
    • প্রথম নোড হিসাবে প্রিনড আপডেট করুন (এটি এখন লেজ হয়ে যাবে)
    • হেড = অস্থায়ী আপডেট করুন যাতে আমরা পারি ঝাঁপ পরের জোড়ায়
  6. তালিকা এখনও হতে পারে শূন্য বা একটি একক আইটেম থাকতে পারে, তাই তালিকার বাকী সাথে প্রডনডটি সংযুক্ত করুন।
  7. প্রয়োজনীয় তালিকা পেতে dummy.next ফিরুন।

বাস্তবায়ন

সি ++ প্রোগ্রাম জোড় লেটকোড দ্রবণে নোড অদলবদল করতে

পুনরাবৃত্তি পদ্ধতির

#include <bits/stdc++.h>
using namespace std;
struct listNode
{
    int value;
    listNode* next;
    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};


void print(listNode* head)
{
    while(head)
    {
        cout << head->value << " ";
        head = head->next;
    }
    cout << '\n';
    return;
}

listNode* swapNodesInPairs(listNode* head)
{
    if(head == NULL || head->next == NULL)
        return head;

    listNode* first = head , *second = head->next;
    first->next = swapNodesInPairs(head->next->next);

    second->next = first;
    return second;
}



int main()
{
    listNode* head = new listNode(1);
    head->next = new listNode(2);
    head->next->next = new listNode(3);

    print(swapNodesInPairs(head));
    return 0;
}

Iterative পদ্ধতির

#include <bits/stdc++.h>
using namespace std;
struct listNode
{
    int value;
    listNode* next;
    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};


void print(listNode* head)
{
    while(head)
    {
        cout << head->value << " ";
        head = head->next;
    }
    cout << '\n';
    return;
}


listNode* swapNodesInPairs(listNode* head)
{
    if(head == NULL || head->next == NULL)
        return head;

    //initialise the prevNode
    listNode *prevNode = new listNode(-1) , *prehead = prevNode;
    prevNode->next = head;


    listNode *first , *second , *temp;
    //temporary variable to store first and second of every pair

    while(head != NULL && head->next != NULL)
    {
        first = head;
        second = head->next;

        temp = second->next;
        second->next = first;
        prevNode->next = second;
        //connecting previous node to the second of this pair


        prevNode = first;
        head = temp;
        //reinitialising previous node and head for next pair
    }

    prevNode->next = head;
    return prehead->next;
}


int main()
{
    listNode* head = new listNode(1);
    head->next = new listNode(2);
    head->next->next = new listNode(3);

    print(swapNodesInPairs(head));
    return 0;
}
2 1 3

জাভা প্রোগ্রাম জোড়া লেটকোড সমাধানগুলিতে নোড অদলবদল করতে

পুনরাবৃত্তি পদ্ধতির

class listNode
{
    int value;
    listNode next;

    listNode(int x)
    {
        value = x;
        next = null;
    }
}

class swap_nodes_in_pairs
{
    public static void print(listNode head)
    {
        while(head != null)
        {
            System.out.print(head.value + " ");
            head = head.next;
        }
        return;
    }

    public static listNode swapNodesInPairs(listNode head)
    {
        if(head == null || head.next == null)
            return head;

        listNode first = head , second = head.next;

        first.next = swapNodesInPairs(head.next.next);
        second.next = first;

        return second;
    }

    public static void main(String args[])
    {
        listNode head = new listNode(1);
        head.next = new listNode(2);
        head.next.next = new listNode(3);
        head.next.next.next = new listNode(4);

        print(swapNodesInPairs(head));
    }
}

Iterative পদ্ধতির

class listNode
{
    int value;
    listNode next;

    listNode(int x)
    {
        value = x;
        next = null;
    }
}

class swap_nodes_in_pairs
{
    public static void print(listNode head)
    {
        while(head != null)
        {
            System.out.print(head.value + " ");
            head = head.next;
        }
        return;
    }

    public static listNode swapNodesInPairs(listNode head)
    {
        if(head == null || head.next == null)
            return head;

        //initialise the prevNode
        listNode prevNode = new listNode(-1) , prehead = prevNode;
        prevNode.next = head;


        listNode first , second , temp;
        //temporary variable to store first and second of every pair

        while(head != null && head.next != null)
        {
            first = head;
            second = head.next;

            temp = second.next;
            second.next = first;
            prevNode.next = second;
            //connecting previous node to the second of this pair


            prevNode = first;
            head = temp;
            //reinitialising previous node and head for next pair
        }

        prevNode.next = head;
        return prehead.next;
    }

    public static void main(String args[])
    {
        listNode head = new listNode(1);
        head.next = new listNode(2);
        head.next.next = new listNode(3);
        head.next.next.next = new listNode(4);

        print(swapNodesInPairs(head));
    }
}
2 1 4 3

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

সময় জটিলতা জোড় নোড পরিবর্তন করতে

পুনরাবৃত্তি পদ্ধতির: চালু), যেমন আমরা তালিকায় কেবল একটি পাস করি। Iterative পদ্ধতির: চালু), আবার আমরা একটি সিঙ্গল পাস।

স্পেস জটিলতা ity জোড় নোড পরিবর্তন করতে

পুনরাবৃত্তি পদ্ধতির: চালু), কারণ পুনরাবৃত্তি মেমরির প্রতিটি কলের জন্য স্ট্যাক ফ্রেম তৈরি করে। Iterative পদ্ধতির: ও (1), ধ্রুবক স্থানটি কিছু ভেরিয়েবলের জন্য ব্যবহৃত হয়। এখানেই পুনরাবৃত্তি পদ্ধতির অবস্থান উত্তম.