กลับ Doubly Linked List เป็นกลุ่มขนาด K ใน C++

ในปัญหานี้ เราได้รับ pointer ไปยัง head ของ Doubly Linked List และจำนวนเต็ม k เราต้องกลับ linked list เป็นกลุ่มขนาด k เช่น:

Input : 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5 (doubly linked list), k = 3 
Output : 3 ↔ 2 ↔ 1 ↔ 5 ↔ 4

แนวทางแก้ปัญหา

ในปัญหานี้ เราจะสร้างอัลกอริทึมแบบ Recursive เพื่อแก้ปัญหานี้

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node *next, *prev;
};

// ฟังก์ชัน push เพื่อเพิ่มโหนดเข้าไปในลิสต์
Node* push(Node* head, int data) {
    Node* new_node = new Node();
    new_node->data = data;
    new_node->next = NULL;
    Node* TMP = head;
    
    if (head == NULL) {
        new_node->prev = NULL;
        head = new_node;
        return head;
    }
    
    while (TMP->next != NULL) {
        TMP = TMP->next;
    }
    TMP->next = new_node;
    new_node->prev = TMP;
    return head;
}

// ฟังก์ชันพิมพ์ลิสต์
void printDLL(Node* head) {
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

Node* revK(Node* head, int k) {
    if (!head)
        return NULL;
    
    head->prev = NULL;
    Node *TMP, *CURRENT = head, *newHead;
    int count = 0;
    
    while (CURRENT != NULL && count < k) {
        newHead = CURRENT;
        TMP = CURRENT->prev;
        CURRENT->prev = CURRENT->next;
        CURRENT->next = TMP;
        CURRENT = CURRENT->prev;
        count++;
    }
    
    if (count >= k) {
        head->next = revK(CURRENT, k);
    }
    
    return newHead;
}

int main() {
    Node* head = NULL;
    for (int i = 1; i <= 5; i++) {
        head = push(head, i);
    }
    
    cout << "Original List : ";
    printDLL(head);
    
    cout << "\nModified List : ";
    int k = 3;
    head = revK(head, k);
    printDLL(head);
    
    return 0;
}

ผลลัพธ์

Original List : 1 2 3 4 5 
Modified List : 3 2 1 5 4

คำอธิบายโค้ด

ในวิธีนี้ เราเดินผ่านลิสต์และกลับลิงก์จนกว่าตัวนับจะถึง k เมื่อถึง k แล้ว เราจะเรียก Recursive ให้ head->next ชี้ไปยัง head ของกลุ่มถัดไปที่ถูกกลับแล้ว

สรุป

ในบทความนี้ เราแก้ปัญหาการกลับ Doubly Linked List เป็นกลุ่มขนาด k ด้วย Recursion เรียนรู้โปรแกรม C++ และแนวทางการแก้ปัญหา สามารถเขียนในภาษาอื่นได้เช่น C, Java, Python หวังว่าจะเป็นประโยชน์