જોડી લેટકોડ સોલ્યુશન્સમાં નોડ્સ સ્વેપ કરો


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એમેઝોન સફરજન બ્લૂમબર્ગ ફેસબુક માઈક્રોસોફ્ટ
લિંક્ડ-સૂચિ

આ સમસ્યાનું લક્ષ્ય આપેલ નોડ્સને અદલાબદલ કરવાનું છે કડી થયેલ યાદી જોડીમાં, એટલે કે, દર બે અડીને ગાંઠો બદલીને. જો અમને સૂચિના ગાંઠોના મૂલ્યમાં ફેરફાર કરવાની મંજૂરી આપવામાં આવે તો, આ સમસ્યા નજીવી હશે. તેથી, અમને નોડ મૂલ્યોમાં ફેરફાર કરવાની મંજૂરી નથી.

ઉદાહરણ

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

અભિગમ

આપણે નોંધ્યું છે કે આપણે જોડીમાં બંને ગાંઠો બદલી શકીએ છીએ. અહીં સ્વેપનો અર્થ પોઇંટર્સને ચાલાકી કરવાનો છે જેથી પ્રથમ નોડ જોડાયેલ સૂચિની બાકીની સાથે જોડાયેલ હોય અને બીજો નોડ હવે બને વડા પ્રથમ નોડ તરફ ઇશારો કરવો.

જોડી લિટકોડ સોલ્યુશન્સમાં સૂચિના ગાંઠો બદલો

આ અદલાબદલ પછીની બાકીની સૂચિ હવે પ્રારંભિક સમસ્યા શું હતી તેની પેટા-સમસ્યા બની જાય છે. તેથી, આપણે બાકીની સૂચિમાં સમાન રિકર્સીવ ફંક્શનને ક callલ કરી શકીએ છીએ. અહીં, આપણે ટ્ર trackક રાખવું જોઈએ કે વડા સૂચિનું હવે ખરેખર સૂચિમાં બીજું નોડ છે. આ એક પર્યાપ્ત સોલ્યુશન છે પરંતુ જગ્યા લે છે કારણ કે રિકર્ઝન મેમરીમાં સ્ટેક ફ્રેમ્સ બનાવે છે.

પુનરાવર્તિત રીતે લાગુ કરવામાં આવતી સમાન અભિગમ તરીકે શ્રેષ્ઠ પદ્ધતિને સરળતાથી વિચારી શકાય છે. આ હેતુ માટે, આપણે એક બનાવવાની જરૂર છે અગાઉના નોડ કે જે અમે પાછલા જોડીની પૂંછડી સંગ્રહિત કરીશું અમે બદલાઇ ગયા. વર્તમાન જોડીના ગાંઠોને અદલાબદલ કર્યા પછી, અમે આ જોડીના માથામાં પાછલી જોડીની પૂંછડીને જોડીએ છીએ.

એલ્ગોરિધમ (પુનરાવર્તિત અભિગમ)

  1. સરળ બેઝની સ્થિતિ ત્યારે હોય છે જ્યારે જોડી બનાવવા માટે બે નોડ પણ હોતા નથી. તે કિસ્સામાં:
    • સૂચિ હોઈ શકે છે NULL અથવા એક આઇટમ સમાવી શકે છે.
    • તે જેમ તે પરત.
  2. હવે આપણી જોડી છે, વાપરો પ્રથમ અને બીજા અમારી જોડીની પ્રથમ અને બીજી વસ્તુઓ સૂચવવા માટે.
  3. ત્યારથી પ્રથમ નોડ હવે આ જોડીની પૂંછડી બની જશે,
    1. આગલી જોડીથી શરૂ થતા પુનરાવર્તિત કાર્યને ક callલ કરો (પછી નોડ બીજા).
    2. સબ પ્રોબ્લેમ ફંકશન દ્વારા હલ કરવામાં આવે છે અને તેને જોડે છે પ્રથમ નોડ
    3. હવે, જોડો પ્રથમ નોડ, જેમાં પણ છે બાકીના તેની સાથે જોડાયેલ સૂચિની, બીજા નોડ પર.
  4. અમે માંગો છો કારણ કે બીજા નોડ સાથે બદલી શકાય છે પ્રથમ દ્વિતીય હવે વડા બનશે,
    1. રીટર્ન બીજું.

અલ્ગોરિધમનો (શ્રેષ્ઠ)

  1. બનાવો અગાઉના કેટલાક ડમી નોડ તરફ નિર્દેશક પોઇન્ટર, તેનું જાળવણી કપાળ.
  2. સેટ આગામી સૂચિના વર્તમાન વડા તરીકે અગાઉના નોડ.
  3. આ પાછલા નિર્દેશક આગામી અદલાબદલ જોડી તરફ નિર્દેશ કરી શકે છે.
  4. જો સૂચિ છે NULL અથવા ફક્ત એક તત્વ છે
    • સૂચિ પરત
  5. જ્યાં સુધી સૂચિ સમાપ્ત થાય છે અથવા ફક્ત એક નોડ બાકી છે ત્યાં સુધી આપણે ત્યાં સુધી પુનરાવર્તન કરો:
    • એમાં આગલી જોડીનું સરનામું સ્ટોર કરો કામચલાઉ ચલ.
    • આ જોડીમાં બે ગાંઠોને સ્વેપ કરો: પ્રથમ નોડ અને બીજો નોડ
    • આ જોડીના બીજા નોડ પર પ્રેપનોડ કનેક્ટ કરો
    • પ્રથમ નોડ તરીકે પ્રેપનોડ અપડેટ કરો (કેમ કે હવે તે પૂંછડી બનશે)
    • અપડેટ હેડ = ટેમ્પ જેથી અમે કરી શકીએ સીધા આના પર જાઓ આગામી જોડી
  6. સૂચિ હજી પણ હોઈ શકે છે NULL અથવા એક વસ્તુ બાકી રહી શકે છે, તેથી બાકીની સૂચિમાં પ્રેપનોડને કનેક્ટ કરો.
  7. જરૂરી સૂચિ મેળવવા માટે ડમી.એનક્સટ પરત કરો.

અમલીકરણ

સી ++ પ્રોગ્રામ જોડીઓ લિટકોડ સોલ્યુશનમાં ગાંઠોને સ્વેપ કરવા માટે

પુનરાવર્તિત અભિગમ

#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 અભિગમ: ઓ (એન), ફરીથી આપણે એક પાસ કરીએ છીએ.

અવકાશ જટિલતા જોડીમાં ગાંઠો અદલાબદલ કરવા માટે

પુનરાવર્તિત અભિગમ: ઓ (એન), જેમ કે રિકર્ઝન મેમરીમાં દરેક ક callલ માટે સ્ટેક ફ્રેમ્સ બનાવે છે. Iterative અભિગમ: ઓ (1), કેમ કે અમુક જગ્યાઓ માટે સતત જગ્યા વપરાય છે. આ તે છે જ્યાં પુનરાવર્તિત અભિગમ છે સારી.