Swap Nodes ในคู่ Leetcode Solutions


ระดับความยาก กลาง
ถามบ่อยใน อเมซอน แอปเปิล บลูมเบิร์ก Facebook ไมโครซอฟท์
รายการที่เชื่อมโยง

เป้าหมายของปัญหานี้คือการสลับโหนดของสิ่งที่กำหนด รายการที่เชื่อมโยง เป็นคู่นั่นคือการแลกเปลี่ยนทุกๆสองโหนดที่อยู่ติดกัน หากเราได้รับอนุญาตให้สลับเฉพาะค่าของโหนดรายการปัญหาจะไม่สำคัญ ดังนั้นเราจึงไม่ได้รับอนุญาตให้แก้ไขค่าโหนด

ตัวอย่าง

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

เข้าใกล้

เราสังเกตได้ว่าเราสามารถสลับสองโหนดเป็นคู่ได้ การแลกเปลี่ยนในที่นี้หมายถึงการจัดการพอยน์เตอร์เพื่อให้โหนดแรกเชื่อมต่อกับส่วนที่เหลือของรายการที่เชื่อมโยงและโหนดที่สองจะกลายเป็น หัว ชี้ไปที่โหนดแรก

สลับโหนดของรายการเป็นคู่ Leetcode Solutions

รายการที่เหลือหลังจากการแลกเปลี่ยนนี้กลายเป็นปัญหาย่อยว่าปัญหาเริ่มต้นคืออะไร ดังนั้นเราสามารถเรียกใช้ฟังก์ชันวนซ้ำเดียวกันกับส่วนที่เหลือของรายการได้ ที่นี่เราต้องติดตามว่าไฟล์ หัว ของรายการตอนนี้เป็นโหนดที่สองในรายการ นี่เป็นวิธีแก้ปัญหาที่เพียงพอ แต่สิ้นเปลืองเนื้อที่เนื่องจากการเรียกซ้ำจะสร้างสแต็กเฟรมในหน่วยความจำ

วิธีการที่เหมาะสมที่สุดสามารถคิดได้ง่ายว่าเป็นวิธีการที่คล้ายกันที่นำไปใช้ซ้ำ ๆ เพื่อจุดประสงค์นี้เราต้องสร้างไฟล์ ก่อน โหนดที่จะเก็บส่วนท้ายของคู่ก่อนหน้านี้ที่เราสลับ หลังจากเปลี่ยนโหนดของคู่ปัจจุบันแล้วเราจะเชื่อมต่อส่วนท้ายของคู่ก่อนหน้ากับส่วนหัวของคู่นี้

อัลกอริทึม (วิธีการเรียกซ้ำ)

  1. เงื่อนไขพื้นฐานง่ายๆคือเมื่อไม่มีสองโหนดที่จะสร้างคู่ ในกรณีนั้น:
    • รายการสามารถ NULL หรืออาจประกอบด้วยรายการเดียว
    • กลับมาเหมือนเดิม
  2. ตอนนี้เรามีคู่ใช้ เป็นครั้งแรก และ ที่สอง เพื่อแสดงถึงรายการแรกและรายการที่สองของคู่ของเรา
  3. ตั้งแต่ เป็นครั้งแรก ตอนนี้โหนดจะกลายเป็นหางของคู่นี้
    1. เรียกฟังก์ชันเรียกซ้ำโดยเริ่มจากคู่ถัดไป (โหนดหลัง ที่สอง).
    2. ปัญหาย่อยได้รับการแก้ไขโดยฟังก์ชันและต่อท้าย เป็นครั้งแรก ปม
    3. ตอนนี้ต่อท้ายไฟล์ เป็นครั้งแรก โหนดซึ่งมีไฟล์ ส่วนที่เหลือ ของรายการที่เชื่อมต่อกับโหนดที่สอง
  4. เนื่องจากเราต้องการ ที่สอง โหนดที่จะสลับกับ ครั้งแรกที่สอง จะกลายเป็นหัวหน้าตอนนี้
    1. กล้บ ที่สอง

อัลกอริทึม (ที่เหมาะสมที่สุด)

  1. สร้าง ก่อน ตัวชี้ที่ชี้ไปยังโหนดดัมมี่บางส่วนให้รักษา พรีเฮด.
  2. ชุด ถัดไป ของโหนดก่อนหน้าเป็นส่วนหัวปัจจุบันของรายการ
  3. ตัวชี้ก่อนหน้านี้สามารถชี้ไปที่คู่ที่สลับถัดไปได้
  4. ถ้าเป็นรายการ NULL หรือมีเพียงองค์ประกอบเดียว
    • กลับรายการ
  5. ทำซ้ำไปเรื่อย ๆ จนกว่าเราจะมาถึงจุดที่รายการสิ้นสุดหรือเหลือเพียงโหนดเดียว:
    • จัดเก็บที่อยู่ของคู่ถัดไปในไฟล์ อุณหภูมิ ตัวแปร
    • สลับสองโหนดในคู่นี้: โหนดแรกและโหนดที่สอง
    • เชื่อมต่อ prevNode กับโหนดที่สองของคู่นี้
    • อัปเดต prevNode เป็นโหนดแรก (เนื่องจากจะกลายเป็นส่วนท้ายในขณะนี้)
    • อัปเดต head = 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 เพื่อสลับโหนดในโซลูชัน 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

การวิเคราะห์ความซับซ้อน

ความซับซ้อนของเวลา เพื่อสลับโหนดเป็นคู่

วิธีการวนซ้ำ: บน)เนื่องจากเราทำเพียงใบเดียวในรายการ วิธีการทำซ้ำ: บน)อีกครั้งเราทำเพียงครั้งเดียว

ความซับซ้อนของอวกาศ เพื่อสลับโหนดเป็นคู่

วิธีการวนซ้ำ: บน)เนื่องจากการเรียกซ้ำจะสร้างสแต็กเฟรมสำหรับทุกการโทรในหน่วยความจำ วิธีการทำซ้ำ: O (1), เนื่องจากใช้พื้นที่คงที่สำหรับตัวแปรบางตัว นี่คือที่มาของวิธีการซ้ำ ดีกว่า.