Reverse Nodes in k-Group ใน C++

สมมติว่าเรามี linked list เราต้องกลับลำดับโหนดของ linked list ทีละ k โหนด และคืนค่ารายการที่แก้ไขแล้ว k เป็นจำนวนเต็มบวกและน้อยกว่าหรือเท่ากับความยาวของ linked list ถ้าจำนวนโหนดไม่ใช่ตัวคูณของ k โหนดที่เหลือท้ายสุดควรคงเดิม

เช่นถ้า linked list คือ [1,2,3,4,5,6,7] และ k คือ 3 ผลลัพธ์จะเป็น [3,2,1,6,5,4,7]

ขั้นตอนการแก้ปัญหา

• กำหนดเมธอด solve() รับหัวของ linked list, partCount และ k
• ถ้า partCount เป็น 0 คืนค่า head
• newHead := head, prev := null, x := k
• while newHead ไม่เป็น null และ x ไม่ใช่ 0
  • temp := next ของ newHead, next ของ newHead := prev
  • prev := newHead, newHead := temp
• next ของ head := solve(newHead, partCount – 1, k)
• คืนค่า prev
• จากเมธอดหลัก
  • คืนค่า solve(หัวของ linked list, ความยาวของ list / k, k)

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

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

void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i < v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}

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));
}

อินพุต

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

เอาต์พุต

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