Đảo ngược nút theo nhóm k trong C++

Cho danh sách liên kết, đảo ngược các nút theo nhóm k và trả về danh sách đã sửa đổi. k là số nguyên dương ≤ độ dài danh sách. Nếu số nút không chia hết cho k, các nút cuối giữ nguyên.

Ví dụ: [1,2,3,4,5,6,7], k = 3 → [3,2,1,6,5,4,7].

Giải thuật (Đệ quy)

• Hàm solve(head, partitionCount, k):
  • Nếu partitionCount == 0 → trả về head.
  • newHead = head, prev = null, x = k.
  • Trong khi newHead != null và x > 0:
    • temp = newHead->next; newHead->next = prev;
    • prev = newHead; newHead = temp; x--.
  • head->next = solve(newHead, partitionCount - 1, k).
  • Trả về prev (đầu mới của nhóm đã đảo).
• Từ main: tính độ dài danh sách, gọi solve(head, length / k, k).

Ví dụ minh họa (C++)

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

class ListNode {
public:
    int val;
    ListNode *next;
    ListNode(int data) { val = data; next = NULL; }
};

ListNode* make_list(vector<int> v) {
    ListNode *head = new ListNode(v[0]);
    for(int i = 1; i < v.size(); i++) {
        ListNode *ptr = head;
        while(ptr->next != NULL) ptr = ptr->next;
        ptr->next = new ListNode(v[i]);
    }
    return head;
}

void print_list(ListNode *head) {
    ListNode *ptr = head;
    cout << "[";
    while(ptr) { cout << ptr->val << ", "; ptr = ptr->next; }
    cout << "]" << endl;
}

class Solution {
public:
    ListNode* solve(ListNode* head, int partitionCount, int k) {
        if(partitionCount == 0) return head;
        ListNode *newHead = head;
        ListNode* prev = NULL;
        ListNode* temp;
        int x = k;
        while(newHead && x--) {
            temp = newHead->next;
            newHead->next = prev;
            prev = newHead;
            newHead = temp;
        }
        head->next = solve(newHead, partitionCount - 1, k);
        return prev;
    }

    int calcLength(ListNode* head) {
        int len = 0;
        ListNode* curr = head;
        while(curr) { len++; curr = curr->next; }
        return len;
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        int length = calcLength(head);
        return solve(head, length / k, k);
    }
};

int main() {
    vector<int> v = {1,2,3,4,5,6,7};
    ListNode *head = make_list(v);
    Solution ob;
    print_list(ob.reverseKGroup(head, 3));
    return 0;
}

Đầu vào

1,2,3,4,5,6,7 3

Đầu ra

[3, 2, 1, 6, 5, 4, 7, ]