تبديل العقد في أزواج حلول Leetcode


مستوى الصعوبة متوسط
كثيرا ما يطلب في أمازون أجهزة آبل بلومبرغ فيسبوك Microsoft
قائمة مرتبطة

الهدف من هذه المشكلة هو تبديل عقد معين قائمة مرتبطة في أزواج ، أي تبديل كل عقدتين متجاورتين. إذا سُمح لنا بتبديل قيمة عقد القائمة فقط ، فستكون المشكلة تافهة. لذلك ، لا يُسمح لنا بتعديل قيم العقدة.

مثال

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

الرسالة

يمكننا ملاحظة أنه يمكننا تبديل العقدتين في زوج. تعني المبادلة هنا معالجة المؤشرات بحيث يتم توصيل العقدة الأولى ببقية القائمة المرتبطة وتصبح العقدة الثانية الآن رئيس مشيرا إلى العقدة الأولى.

تبديل العقد لقائمة في أزواج حلول Leetcode

أصبحت القائمة المتبقية بعد هذا التبادل الآن مشكلة فرعية لما كانت المشكلة الأولية. لذلك ، يمكننا استدعاء نفس الدالة العودية لبقية القائمة. هنا ، يجب أن نتتبع أن ملف رئيس من القائمة هي الآن العقدة الثانية في القائمة. هذا حل كافٍ ولكنه يستهلك مساحة لأن العودية تخلق إطارات مكدسة في الذاكرة.

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

الخوارزمية (نهج تكراري)

  1. الشروط الأساسية البسيطة هي عندما لا يكون لديك حتى عقدتان لتكوين زوج. في هذه الحالة:
    • يمكن أن تكون القائمة اغية أو يمكن أن تشتمل على عنصر واحد.
    • إعادته كما هو.
  2. الآن بعد أن أصبح لدينا زوج ، استخدم أول و ثان للدلالة على العناصر الأولى والثانية من زوجنا.
  3. منذ أول ستصبح العقدة الآن ذيل هذا الزوج ،
    1. قم باستدعاء الوظيفة العودية بدءًا من الزوج التالي (العقدة بعد ثان).
    2. يتم حل المشكلة الفرعية بواسطة الوظيفة وإلحاقها بها أول العقدة.
    3. الآن ، قم بإلحاق ملف أول العقدة ، والتي لها أيضًا الامتداد بقية من القائمة المتصلة به ، إلى العقدة الثانية.
  4. لأننا نريد ثان العقدة المراد مبادلتها الثانية الأولى سيصبح رأسا الآن ،
    1. الإرجاع ثانيا.

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

  1. إنشاء سابق مؤشر يشير إلى بعض العقدة الوهمية ، والحفاظ على جبهته.
  2. ضبط التالي من العقدة السابقة كرئيس حالي للقائمة.
  3. يمكن أن يشير هذا المؤشر السابق إلى الزوج المبادل التالي.
  4. إذا كانت القائمة اغية أو يحتوي على عنصر واحد فقط
    • إعادة القائمة
  5. استمر في التكرار حتى نصل إلى نقطة تنتهي عندها القائمة أو يتبقى فيها عقدة واحدة فقط:
    • قم بتخزين عنوان الزوج التالي في ملف درجة الحرارة المتغير.
    • قم بتبديل العقدتين في هذا الزوج: العقدة الأولى والعقدة الثانية
    • قم بتوصيل prevNode بالعقدة الثانية لهذا الزوج
    • قم بتحديث prevNode باعتباره العقدة الأولى (حيث ستصبح الذيل الآن)
    • تحديث head = temp حتى نتمكن من ذلك قفز للزوج التالي
  6. لا تزال القائمة اغية أو يمكن ترك عنصر واحد ، لذلك قم بتوصيل prevNode ببقية القائمة.
  7. عودة dummy.next للحصول على القائمة المطلوبة.

تطبيق

برنامج C ++ لمبادلة العقد في حل leetcode الأزواج

النهج التكراري

#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;
}

نهج تكراري

#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

برنامج Java لمبادلة العقد في أزواج حلول leetcode

النهج التكراري

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));
    }
}

نهج تكراري

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

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

تعقيد الوقت لمبادلة العقد في أزواج

النهج التكراري: على)، لأننا نقوم بتمريرة واحدة فقط في القائمة. نهج تكراري: على)، مرة أخرى نقوم بتمريرة واحدة.

تعقيد الفضاء لمبادلة العقد في أزواج

النهج التكراري: على)، لأن العودية تنشئ إطارات مكدسة لكل مكالمة في الذاكرة. نهج تكراري: يا (1) ، كمساحة ثابتة تستخدم لبعض المتغيرات. هذا هو المكان الذي يوجد فيه النهج التكراري أفضل.