ਪੇਅਰਜ਼ ਲੈਟਕੋਡ ਸਲਿ .ਸ਼ਨਜ਼ ਵਿਚ ਨੋਡਾਂ ਨੂੰ ਸਵੈਪ ਕਰੋ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਦਰਮਿਆਨੇ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ ਸੇਬ ਬਲੂਮਬਰਗ ਫੇਸਬੁੱਕ Microsoft ਦੇ
ਲਿੰਕਡ-ਲਿਸਟ

ਇਸ ਸਮੱਸਿਆ ਦਾ ਟੀਚਾ ਇੱਕ ਦਿੱਤੇ ਨੋਡਾਂ ਨੂੰ ਬਦਲਣਾ ਹੈ ਲਿੰਕਡ ਸੂਚੀ ਜੋੜਿਆਂ ਵਿਚ, ਭਾਵ, ਹਰ ਦੋ ਨਾਲ ਲੱਗਦੇ ਨੋਡਾਂ ਨੂੰ ਬਦਲਣਾ. ਜੇ ਸਾਨੂੰ ਸੂਚੀ ਨੋਡਾਂ ਦਾ ਮੁੱਲ ਬਦਲਣ ਦੀ ਇਜਾਜ਼ਤ ਹੈ, ਤਾਂ ਇਹ ਸਮੱਸਿਆ ਮਾਮੂਲੀ ਜਿਹੀ ਹੋਵੇਗੀ. ਸੋ, ਸਾਨੂੰ ਨੋਡ ਵੈਲਯੂਜ ਨੂੰ ਸੋਧਣ ਦੀ ਆਗਿਆ ਨਹੀਂ ਹੈ.

ਉਦਾਹਰਨ

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

ਪਹੁੰਚ

ਅਸੀਂ ਨੋਟਿਸ ਕਰ ਸਕਦੇ ਹਾਂ ਕਿ ਅਸੀਂ ਦੋਵੇਂ ਨੋਡਾਂ ਨੂੰ ਇੱਕ ਜੋੜਾ ਵਿੱਚ ਬਦਲ ਸਕਦੇ ਹਾਂ. ਇੱਥੇ ਸਵੈਪ ਦਾ ਮਤਲਬ ਪੁਆਇੰਟਰਾਂ ਵਿੱਚ ਹੇਰਾਫੇਰੀ ਕਰਨਾ ਹੈ ਤਾਂ ਕਿ ਪਹਿਲਾਂ ਨੋਡ ਲਿੰਕ ਕੀਤੀ ਸੂਚੀ ਦੇ ਬਾਕੀ ਹਿੱਸੇ ਨਾਲ ਜੁੜਿਆ ਹੋਵੇ ਅਤੇ ਦੂਜਾ ਨੋਡ ਹੁਣ ਬਣ ਜਾਵੇ ਸਿਰ ਪਹਿਲੇ ਨੋਡ ਵੱਲ ਇਸ਼ਾਰਾ ਕਰਨਾ.

ਜੋੜੀ ਲੇਟਕੋਡ ਸਲਿ .ਸ਼ਨਜ਼ ਦੀ ਸੂਚੀ ਦੇ ਨੋਡ ਬਦਲੋ

ਇਸ ਸਵੈਪ ਤੋਂ ਬਾਅਦ ਬਾਕੀ ਸੂਚੀ ਹੁਣ ਇਕ ਸਬ-ਸਮੱਸਿਆ ਬਣ ਜਾਂਦੀ ਹੈ ਕਿ ਸ਼ੁਰੂਆਤੀ ਸਮੱਸਿਆ ਕੀ ਸੀ. ਇਸ ਲਈ, ਅਸੀਂ ਉਹੀ ਰਿਕਰਸਿਵ ਫੰਕਸ਼ਨ ਨੂੰ ਬਾਕੀ ਸੂਚੀ ਵਿਚ ਕਾਲ ਕਰ ਸਕਦੇ ਹਾਂ. ਇੱਥੇ, ਸਾਨੂੰ ਇਹ ਯਾਦ ਰੱਖਣਾ ਚਾਹੀਦਾ ਹੈ ਕਿ ਸਿਰ ਸੂਚੀ ਦਾ ਅਸਲ ਵਿੱਚ ਸੂਚੀ ਵਿੱਚ ਦੂਜਾ ਨੋਡ ਹੈ. ਇਹ ਇੱਕ ਕਾਫ਼ੀ ਹੱਲ ਹੈ ਪਰ ਸਪੇਸ ਖਪਤ ਕਰਦਾ ਹੈ ਕਿਉਂਕਿ ਰੀਵਰਸਨ ਮੈਮੋਰੀ ਵਿੱਚ ਸਟੈਕ ਫਰੇਮ ਬਣਾਉਂਦਾ ਹੈ.

ਅਨੁਕੂਲ methodੰਗ ਨੂੰ ਆਸਾਨੀ ਨਾਲ ਸੋਚਿਆ ਜਾ ਸਕਦਾ ਹੈ ਜਿਵੇਂ ਕਿ ਦੁਬਾਰਾ ਲਾਗੂ ਕੀਤੀ ਗਈ ਇਕੋ ਜਿਹੀ ਪਹੁੰਚ. ਇਸ ਉਦੇਸ਼ ਲਈ, ਸਾਨੂੰ ਇੱਕ ਬਣਾਉਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ ਪਿਛਲੇ ਨੋਡ ਜੋ ਪਿਛਲੀ ਜੋੜੀ ਦੀ ਪੂਛ ਨੂੰ ਸਟੋਰ ਕਰੇਗਾ ਜੋ ਅਸੀਂ ਬਦਲਿਆ. ਮੌਜੂਦਾ ਜੋੜੀ ਦੇ ਨੋਡਾਂ ਨੂੰ ਬਦਲਣ ਤੋਂ ਬਾਅਦ, ਅਸੀਂ ਪਿਛਲੇ ਜੋੜੀ ਦੀ ਪੂਛ ਨੂੰ ਇਸ ਜੋੜੀ ਦੇ ਸਿਰ ਜੋੜਦੇ ਹਾਂ.

ਐਲਗੋਰਿਦਮ (ਰਿਕਰਸਿਵ ਪਹੁੰਚ)

  1. ਸਧਾਰਣ ਬੇਸ ਹਾਲਤਾਂ ਉਹ ਹੁੰਦੀਆਂ ਹਨ ਜਦੋਂ ਇਕ ਜੋੜਾ ਬਣਾਉਣ ਲਈ ਦੋ ਨੋਡ ਵੀ ਨਹੀਂ ਹੁੰਦੇ. ਉਸ ਹਾਲਤ ਵਿੱਚ:
    • ਸੂਚੀ ਹੋ ਸਕਦੀ ਹੈ NULL ਜਾਂ ਇਕ ਵਸਤੂ ਸ਼ਾਮਲ ਕਰ ਸਕਦਾ ਹੈ.
    • ਇਸ ਨੂੰ ਇਸ ਨੂੰ ਵਾਪਸ ਕਰੋ.
  2. ਹੁਣ ਜਦੋਂ ਸਾਡੀ ਜੋੜੀ ਹੈ, ਵਰਤੋਂ ਪਹਿਲੀ ਅਤੇ ਦੂਜਾ ਸਾਡੀ ਜੋੜੀ ਦੇ ਪਹਿਲੇ ਅਤੇ ਦੂਜੇ ਆਈਟਮ ਨੂੰ ਦਰਸਾਉਣ ਲਈ.
  3. ਕਿਉਕਿ ਪਹਿਲੀ ਨੋਡ ਹੁਣ ਇਸ ਜੋੜੀ ਦੀ ਪੂਛ ਬਣ ਜਾਵੇਗਾ,
    1. ਅਗਲੀ ਜੋੜੀ ਤੋਂ ਸ਼ੁਰੂ ਹੋਣ ਵਾਲੇ ਰਿਕਰਸਿਵ ਫੰਕਸ਼ਨ ਨੂੰ ਕਾਲ ਕਰੋ (ਬਾਅਦ ਵਿਚ ਨੋਡ ਦੂਜਾ).
    2. ਸਬਪ੍ਰਬਲਮ ਫੰਕਸ਼ਨ ਦੁਆਰਾ ਹੱਲ ਕੀਤਾ ਜਾਂਦਾ ਹੈ ਅਤੇ ਇਸਨੂੰ ਜੋੜਦਾ ਹੈ ਪਹਿਲੀ ਨੋਡ
    3. ਹੁਣ, ਸ਼ਾਮਿਲ ਕਰੋ ਪਹਿਲੀ ਨੋਡ, ਜਿਸ ਵਿਚ ਇਹ ਵੀ ਹੈ ਬਾਕੀ ਦੂਜੇ ਨੋਡ ਨਾਲ ਇਸ ਨਾਲ ਜੁੜੀ ਸੂਚੀ ਦੀ.
  4. ਕਿਉਂਕਿ ਅਸੀਂ ਚਾਹੁੰਦੇ ਹਾਂ ਦੂਜਾ ਨੋਡ ਨਾਲ ਤਬਦੀਲ ਹੋਣਾ ਹੈ ਪਹਿਲਾ, ਦੂਜਾ ਹੁਣ ਸਿਰ ਬਣ ਜਾਵੇਗਾ,
    1. ਵਾਪਸੀ ਦੂਜਾ

ਐਲਗੋਰਿਦਮ (ਅਨੁਕੂਲ)

  1. ਇੱਕ ਬਣਾਓ ਪਿਛਲੇ ਪੁਆਇੰਟਰ ਕੁਝ ਡੰਮੀ ਨੋਡ ਵੱਲ ਇਸ਼ਾਰਾ ਕਰ ਰਿਹਾ ਹੈ, ਇਸ ਨੂੰ ਬਣਾਈ ਰੱਖੋ ਮੱਥੇ.
  2. ਸੈੱਟ ਕਰੋ ਅਗਲੇ ਸੂਚੀ ਦੇ ਮੌਜੂਦਾ ਮੁਖੀ ਵਜੋਂ ਪਿਛਲੇ ਨੋਡ ਦੇ.
  3. ਇਹ ਪਿਛਲਾ ਪੁਆਇੰਟਰ ਅਗਲੀ ਸਵੈਪਡ ਜੋੜੀ ਵੱਲ ਇਸ਼ਾਰਾ ਕਰ ਸਕਦਾ ਹੈ.
  4. ਜੇ ਸੂਚੀ ਹੈ NULL ਜਾਂ ਸਿਰਫ ਇਕ ਤੱਤ ਹੈ
    • ਸੂਚੀ ਵਾਪਸ
  5. ਦੁਹਰਾਉਂਦੇ ਰਹੋ ਜਦੋਂ ਤਕ ਅਸੀਂ ਇਕ ਬਿੰਦੂ ਤੇ ਨਾ ਪਹੁੰਚੀਏ ਜਿਥੇ ਸੂਚੀ ਖਤਮ ਹੋ ਜਾਂਦੀ ਹੈ ਜਾਂ ਸਿਰਫ ਇਕ ਨੋਡ ਬਚਿਆ ਹੈ:
    • ਅਗਲੀ ਜੋੜੀ ਦਾ ਪਤਾ ਏ ਵਿੱਚ ਸਟੋਰ ਕਰੋ ਅਸਥਾਈ ਵੇਰੀਏਬਲ.
    • ਇਸ ਜੋੜੀ ਵਿਚ ਦੋ ਨੋਡਾਂ ਨੂੰ ਸਵੈਪ ਕਰੋ: ਪਹਿਲਾਂ ਨੋਡ ਅਤੇ ਦੂਜਾ ਨੋਡ
    • ਇਸ ਜੋੜੀ ਦੇ ਦੂਜੇ ਨੋਡ ਨਾਲ ਪ੍ਰਪਨ ਨੋਡ ਨੂੰ ਜੋੜੋ
    • ਪਹਿਲੇ ਨੋਡ ਦੇ ਤੌਰ ਤੇ ਐਡਵੋਡ ਕਰੋ (ਜਿਵੇਂ ਕਿ ਇਹ ਹੁਣ ਪੂਛ ਬਣ ਜਾਵੇਗਾ)
    • ਅਪਡੇਟ ਹੈਡ = ਅਸਥਾਈ ਤਾਂ ਜੋ ਅਸੀਂ ਕਰ ਸਕੀਏ ਛਾਲ ਅਗਲੀ ਜੋੜੀ ਨੂੰ
  6. ਸੂਚੀ ਅਜੇ ਵੀ ਹੋ ਸਕਦੀ ਹੈ NULL ਜਾਂ ਇਕੋ ਇਕਾਈ ਰਹਿ ਸਕਦੀ ਹੈ, ਇਸ ਲਈ ਬਾਕੀ ਸੂਚੀ ਨੂੰ ਨਾਲ ਜੋੜੋ.
  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 ਪਹੁੰਚ: ਓ (ਐਨ), ਫੇਰ ਅਸੀਂ ਇੱਕ ਪਾਸ ਕਰਦੇ ਹਾਂ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ ਜੋੜਿਆਂ ਵਿਚ ਨੋਡਾਂ ਨੂੰ ਬਦਲਣਾ

ਰਿਕਰਸਿਵ ਪਹੁੰਚ: ਓ (ਐਨ), ਜਿਵੇਂ ਕਿ ਦੁਹਰਾਓ ਯਾਦ ਵਿੱਚ ਹਰ ਕਾਲ ਲਈ ਸਟੈਕ ਫਰੇਮ ਬਣਾਉਂਦਾ ਹੈ. Iterative ਪਹੁੰਚ: ਓ (1), ਕਿਉਂਕਿ ਸਥਿਰ ਸਪੇਸ ਕੁਝ ਵੇਰੀਏਬਲਸ ਲਈ ਵਰਤੀ ਜਾਂਦੀ ਹੈ. ਇਹ ਉਹ ਥਾਂ ਹੈ ਜਿਥੇ ਦੁਹਰਾਉਣ ਵਾਲੀ ਪਹੁੰਚ ਹੈ ਬਿਹਤਰ.