题解 | #牛群的重新分组#

将链表中的数据提取到带有序号的映射中，然后将节点交换，最后按交换后的顺序放入向量中组合成符合题目要求的链表。

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
private:
    map<int, ListNode*> map;
    vector<ListNode*> list;
    int group = 0;
    int length = 0;
    int count = 0;
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        calLength(head);
        group = length / k;
        collect(head);
        count = 0;
        reverse(k);
        head = list.at(0);
        count = 1;
        creat(head);
        return head;
    }

    void calLength(ListNode* head) {
        length++;
        if(head->next == nullptr) {
            return;
        }
        calLength(head->next);
    }

    void collect(ListNode* head) {
        map.insert({count, head});
        count++;
        if(head->next == nullptr) {
            return;
        }
        collect(head->next);
    }

    void reverse(int k) {
        for(int i = 0; i < group; i++) {
            for(int j = (i + 1) * k - 1; j >= (i + 1) * k - k; j--) {
                list.push_back(map.at(j));
                count++;
            }
        }
        //if(count < length - 1) {
            for(int i = count; i < length; i++) {
                list.push_back(map.at(i));
            }
        //}
    }

    void creat(ListNode* head) {
        head->next = list.at(count);
        if(count == list.size() - 1) {
            head->next->next = nullptr;
        }
        count++;
        if(count < list.size()) {
            creat(head->next);
        }
    }
};