Swap Nodes ໃນ Pairs Leetcode Solutions


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Amazon ຈາກຫນາກແອບເປີ Bloomberg ເຟສບຸກ Microsoft
ບັນຊີທີ່ເຊື່ອມໂຍງ

ເປົ້າ ໝາຍ ຂອງປັນຫານີ້ແມ່ນເພື່ອແລກປ່ຽນຂໍ້ທີ່ໄດ້ຮັບ ບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງ ໃນຄູ່, ນັ້ນແມ່ນ, ການແລກປ່ຽນທຸກໆສອງຂໍ້ທີ່ຢູ່ຕິດກັນ. ຖ້າພວກເຮົາໄດ້ຮັບອະນຸຍາດໃຫ້ແລກປ່ຽນພຽງແຕ່ມູນຄ່າຂອງຂໍ້ມູນບັນຊີ, ບັນຫາຈະເປັນເລື່ອງເລັກໆນ້ອຍໆ. ດັ່ງນັ້ນ, ພວກເຮົາບໍ່ໄດ້ຮັບອະນຸຍາດໃຫ້ດັດແປງຄ່າ node.

ຍົກຕົວຢ່າງ

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

ວິທີການ

ພວກເຮົາສາມາດສັງເກດເຫັນວ່າພວກເຮົາສາມາດແລກປ່ຽນສອງຂໍ້ດັ່ງກ່າວເປັນຄູ່. ການແລກປ່ຽນຢູ່ທີ່ນີ້ ໝາຍ ຄວາມວ່າຈະ ໝູນ ໃຊ້ຈຸດຊີ້ເພື່ອໃຫ້ຂໍ້ ທຳ ອິດເຊື່ອມຕໍ່ກັບສ່ວນທີ່ເຫຼືອຂອງບັນຊີທີ່ເຊື່ອມໂຍງແລະຂໍ້ທີ່ສອງຕອນນີ້ກາຍເປັນ ຫົວຫນ້າ ຊີ້ໄປທີ່ຂໍ້ ທຳ ອິດ.

ແລກປ່ຽນ Nodes ຂອງບັນຊີລາຍຊື່ໃນຄູ່ Leetcode Solutions

ບັນຊີລາຍຊື່ທີ່ຍັງເຫຼືອຫຼັງຈາກການແລກປ່ຽນປະຈຸບັນກາຍເປັນບັນຫາຍ່ອຍຂອງບັນຫາເບື້ອງຕົ້ນ. ດັ່ງນັ້ນ, ພວກເຮົາສາມາດໂທຫາຟັງຊັນເອີ້ນຫາດຽວກັນກັບສ່ວນທີ່ເຫຼືອ. ນີ້, ພວກເຮົາຕ້ອງຕິດຕາມວ່າ ຫົວຫນ້າ ຂອງບັນຊີແມ່ນຕົວຈິງແລ້ວແມ່ນຂໍ້ທີສອງໃນບັນຊີ. ນີ້ແມ່ນວິທີແກ້ໄຂທີ່ພຽງພໍແຕ່ກິນພື້ນທີ່ເພາະວ່າການຄົ້ນຫາຄືນ ໃໝ່ ສ້າງກອບເຟືອງໃນ ໜ່ວຍ ຄວາມ ຈຳ.

ວິທີການທີ່ດີທີ່ສຸດສາມາດຄິດໄດ້ງ່າຍວ່າວິທີການທີ່ຄ້າຍຄືກັນນີ້ໄດ້ຖືກຈັດຕັ້ງປະຕິບັດ. ເພື່ອຈຸດປະສົງນີ້, ພວກເຮົາຕ້ອງການສ້າງ a ທີ່ຜ່ານມາ node ທີ່ຈະເກັບຫາງຂອງພຽງແຕ່ຄູ່ທີ່ຜ່ານມາພວກເຮົາໄດ້ແລກປ່ຽນກັນ. ຫຼັງຈາກແລກປ່ຽນຂໍ້ຂອງຂໍ້ຂອງຄູ່ປັດຈຸບັນ, ພວກເຮົາເຊື່ອມຕໍ່ຫາງຂອງຄູ່ກ່ອນ ໜ້າ ນີ້ໃສ່ຫົວຂອງຄູ່ນີ້.

ສູດການຄິດໄລ່ (ວິທີການອ້າງອິງ)

  1. ເງື່ອນໄຂພື້ນຖານທີ່ງ່າຍດາຍແມ່ນເວລາທີ່ບໍ່ມີທັງສອງຂໍ້ເພື່ອປະກອບເປັນຄູ່. ໃນ​ກໍ​ລະ​ນີ​ນັ້ນ:
    • ບັນຊີລາຍຊື່ສາມາດເປັນໄດ້ NULL ຫຼືສາມາດປະກອບມີ ໜຶ່ງ ລາຍການ.
    • ສົ່ງຄືນມັນເປັນມັນ.
  2. ໃນປັດຈຸບັນທີ່ພວກເຮົາມີຄູ່, ໃຊ້ ຄັ້ງທໍາອິດ ແລະ ຄັ້ງທີສອງ ໝາຍ ເຖິງລາຍການທີ ໜຶ່ງ ແລະສອງຂອງຄູ່ຂອງພວກເຮົາ.
  3. ນັບຕັ້ງແຕ່ ຄັ້ງທໍາອິດ ຕອນນີ້ຈະກາຍເປັນຫາງຂອງຄູ່ນີ້,
    1. ໂທຫາຟັງຊັນທີ່ເອີ້ນຫາເລີ່ມຕົ້ນຈາກຄູ່ຕໍ່ໄປ (node ​​ຫຼັງຈາກ ຄັ້ງທີສອງ).
    2. ຮູບແບບຍ່ອຍແມ່ນຖືກແກ້ໄຂໂດຍ ໜ້າ ທີ່ແລະເພີ່ມເຕີມໃຫ້ ຄັ້ງທໍາອິດ ຂໍ້.
    3. ໃນປັດຈຸບັນ, ເພີ່ມເຕີມ ຄັ້ງທໍາອິດ ຂໍ້, ເຊິ່ງຍັງມີ ສ່ວນທີ່ເຫຼືອ ຂອງບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ກັບມັນ, ກັບຂໍ້ທີສອງ.
  4. ນັບຕັ້ງແຕ່ພວກເຮົາຕ້ອງການ ຄັ້ງທີສອງ node ທີ່ຈະຖືກແລກປ່ຽນກັບ ຄັ້ງທີ ໜຶ່ງ, ທີສອງ ຈະກາຍເປັນຫົວຫນ້າໃນປັດຈຸບັນ,
    1. Return ຄັ້ງທີສອງ.

ສູດການຄິດໄລ່ (ດີທີ່ສຸດ)

  1. ສ້າງເປັນ ທີ່ຜ່ານມາ pointer ຊີ້ໄປຫາ nummy dode ບາງ, ຮັກສາມັນ ກ່ອນກ່ອນເວລາ.
  2. ທີ່ກໍານົດໄວ້ ຕໍ່ໄປ ຂອງຂໍ້ທີ່ຜ່ານມາເປັນຫົວ ໜ້າ ປະຈຸບັນ.
  3. ຕົວຊີ້ທີ່ຜ່ານມານີ້ສາມາດຊີ້ໄປທີ່ຄູ່ແລກປ່ຽນຕໍ່ໄປ.
  4. ຖ້າບັນຊີແມ່ນ NULL ຫຼືມີພຽງແຕ່ອົງປະກອບດຽວ
    • ສົ່ງຄືນລາຍຊື່
  5. ຮັກສາຄວາມຊື້ນ້ ຳ ໃຈຈົນກວ່າພວກເຮົາຈະໄປຮອດຈຸດທີ່ລາຍຊື່ຈະສິ້ນສຸດລົງຫຼືມີພຽງ ໜຶ່ງ ຂໍ້ເທົ່ານັ້ນ:
    • ເກັບຮັກສາທີ່ຢູ່ຂອງຄູ່ຕໍ່ໄປໃນກ ວັດລົມ ຕົວແປ.
    • ແລກປ່ຽນສອງຂໍ້ໃນຄູ່ນີ້: ຂໍ້ ທຳ ອິດແລະຂໍ້ທີສອງ
    • ເຊື່ອມຕໍ່ prevNode ກັບຂໍ້ທີສອງຂອງຄູ່ນີ້
    • ປັບປຸງ prevNode ເປັນຂໍ້ ທຳ ອິດ (ຍ້ອນວ່າມັນຈະກາຍເປັນຫາງດຽວນີ້)
    • ປັບປຸງຫົວ = temp ເພື່ອໃຫ້ພວກເຮົາສາມາດເຮັດໄດ້ ເຕັ້ນໄປຫາ ກັບຄູ່ຕໍ່ໄປ
  6. ບັນຊີລາຍຊື່ຍັງສາມາດເປັນໄດ້ NULL ຫຼືສາມາດມີລາຍການດຽວທີ່ຍັງເຫຼືອ, ສະນັ້ນເຊື່ອມຕໍ່ 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 Program ໃນການແລກປ່ຽນຂໍ້ມູນເປັນຄູ່ໃນໂຊລູຊັ່ນ 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

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ ເພື່ອປ່ຽນເສັ້ນໃຍເປັນຄູ່

ວິທີການແບບທົດແທນ: ໂອ (N), ດັ່ງທີ່ພວກເຮົາເຮັດຜ່ານດຽວໃນບັນຊີ. ວິທີການຄິດໄລ່: ໂອ (N), ອີກເທື່ອຫນຶ່ງພວກເຮົາເຮັດຜ່ານດຽວ.

ຄວາມສັບສົນໃນອະວະກາດ ເພື່ອປ່ຽນເສັ້ນໃຍເປັນຄູ່

ວິທີການແບບທົດແທນ: ໂອ (N), ເປັນການເອີ້ນຄືນການສ້າງກອບເຟືອງ ສຳ ລັບທຸກໆການໂທໃນຄວາມຊົງ ຈຳ. ວິທີການຄິດໄລ່: ໂອ (1), ເປັນພື້ນທີ່ຄົງທີ່ຖືກໃຊ້ ສຳ ລັບຕົວແປບາງຢ່າງ. ນີ້ແມ່ນບ່ອນທີ່ວິທີການປ່ຽນແປງແມ່ນ ດີກວ່າ.