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

ในบทความนี้ เราจัดการกับ Singly Linked List โดยมีงานคือการกลับลิสต์เป็นกลุ่มขนาด k เช่น:

Input: 1→2→3→4→5→6→7→8→NULL, K = 3 
Output: 3→2→1→6→5→4→8→7→NULL

Input: 1→2→3→4→5→6→7→8→NULL, K = 5 
Output: 5→4→3→2→1→8→7→6→NULL

สำหรับปัญหานี้ วิธีหนึ่งคือเดินผ่านลิสต์และกลับลิสต์เมื่อขนาด sublist ถึง k แล้วทำต่อไป

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

ในวิธีนี้ เราจะเดินผ่านลิสต์โดยทั่วไป และนับจำนวนสมาชิกใน sublist ด้วยตัวนับ เมื่อตัวนับถึง k เราจะกลับส่วนนั้น

ตัวอย่างโค้ด (ใช้ Recursion)

#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    int data;
    Node* next;
};

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

void push(Node** head_ref, int new_data) {
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

void printList(Node* node) {
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
    cout << "\n";
}

int main() {
    Node* head = NULL;
    int k = 3;
    push(&head, 8);
    push(&head, 7);
    push(&head, 6);
    push(&head, 5);
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);
    
    cout << "Original list \n";
    printList(head);
    
    head = reverse(head, k);
    
    cout << "New list \n";
    printList(head);
    
    return 0;
}

ผลลัพธ์

Original list 
1 2 3 4 5 6 7 8 
New list 
3 2 1 6 5 4 8 7

วิธีนี้มี Time Complexity เป็น O(N) โดย N คือขนาดของลิสต์ และทำงานแบบ Recursive

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

เราเดินผ่านลิสต์และกลับลิงก์จนกว่าตัวนับจะถึง k เมื่อถึง k แล้ว เราจะเรียกฟังก์ชัน reverse อีกครั้งเพื่อเชื่อมโหนดสุดท้ายของ sublist นี้กับโหนดแรกของ sublist ถัดไปที่ถูกกลับแล้ว ทำได้ด้วย Recursion

สรุป

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