جوڑیں لیٹکوڈ حل میں نوڈس کو تبدیل کریں


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایمیزون ایپل بلومبرگ فیس بک مائیکروسافٹ
لنکڈ لسٹ

اس پریشانی کا مقصد یہ ہے کہ دیئے گئے نوڈس کو تبدیل کیا جائے منسلک فہرست جوڑے میں ، یعنی ، ہر دو ملحقہ نوڈس کو تبدیل کرنا۔ اگر ہمیں فہرست کے نوڈس کی قدر کی تبادلہ کرنے کی اجازت دی جاتی ہے تو ، یہ مسئلہ معمولی ہوجائے گا۔ لہذا ، ہمیں نوڈ کی قدروں میں ترمیم کرنے کی اجازت نہیں ہے۔

مثال کے طور پر

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

نقطہ نظر

ہم محسوس کرسکتے ہیں کہ ہم دونوں نوڈس کو ایک جوڑے میں بدل سکتے ہیں۔ یہاں تبادلہ کا مطلب پوائنٹس میں ہیرا پھیری کرنا ہے تاکہ پہلا نوڈ منسلک فہرست کے باقی حصے سے جڑا ہوا ہو اور دوسرا نوڈ اب بن جائے سر پہلے نوڈ کی طرف اشارہ کرتے ہوئے۔

جوڑے لیٹ کوڈ حل میں فہرست کے نوڈس کو تبدیل کریں

اس تبادلہ کے بعد باقی فہرست اب ذیلی مسئلہ بن جاتی ہے کہ ابتدائی پریشانی کیا تھی۔ لہذا ، ہم باقی فہرست میں اسی تکرار والے فنکشن کو کال کرسکتے ہیں۔ یہاں ، ہمیں معلوم رکھنا چاہئے کہ سر فہرست میں اب دراصل فہرست میں دوسرا نوڈ ہے۔ یہ ایک کافی حل ہے لیکن جگہ استعمال کرتا ہے کیونکہ تکرار کرنے سے میموری میں اسٹیک فریم پیدا ہوتا ہے۔

اسی طرح کے نقطہ نظر کو مکرر طور پر نافذ کرنے کے بعد ہی بہتر طریقہ پر آسانی سے سوچا جاسکتا ہے۔ اس مقصد کے لئے ، ہمیں ایک تشکیل دینے کی ضرورت ہے پچھلا نوڈ جو ہم نے تبدیل کیا ہے صرف پچھلے جوڑے کی دم جمع کرے گا۔ موجودہ جوڑی کے نوڈس کو تبدیل کرنے کے بعد ، ہم پچھلے جوڑے کی دم کو اس جوڑی کے سر سے جوڑ دیتے ہیں۔

الگورتھم (پنرقوی نقطہ نظر)

  1. سادہ بنیادی شرائط ایسے وقت ہوتی ہیں جب جوڑی بنانے کے لئے دو نوڈس بھی نہیں ہوتے ہیں۔ اس صورت میں:
    • فہرست ہوسکتی ہے خالی یا ایک آئٹم پر مشتمل ہوسکتا ہے۔
    • اسے جیسے ہی لوٹا دو۔
  2. اب جبکہ ہمارے پاس جوڑی ہے ، استعمال کریں سب سے پہلے اور دوسری ہماری جوڑی کی پہلی اور دوسری اشیاء کو ظاہر کرنا۔
  3. چونکہ سب سے پہلے نوڈ اب اس جوڑے کی دم بن جائے گا ،
    1. اگلی جوڑی سے شروع ہونے والی تکرار والی تقریب کو کال کریں (کے بعد نوڈ دوسری).
    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

پیچیدگی کا تجزیہ

وقت کی پیچیدگی جوڑے میں نوڈس کو تبدیل کرنے کے لئے

تکرار نقطہ نظر: O (N)، جیسا کہ ہم صرف فہرست میں ایک ہی پاس کرتے ہیں۔ Iterative نقطہ نظر: O (N)، پھر ہم ایک ہی پاس کرتے ہیں۔

خلائی پیچیدگی جوڑے میں نوڈس کو تبدیل کرنے کے لئے

تکرار نقطہ نظر: O (N)، چونکہ تکرار یادداشت میں ہر کال کے لئے اسٹیک فریم تیار کرتی ہے۔ Iterative نقطہ نظر: O (1) ، چونکہ کچھ جگہوں کے لئے مستقل جگہ استعمال ہوتی ہے۔ یہ ہے جہاں مکرر نقطہ نظر ہے بہتر.