/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/*
1, 统计head节点个数为cnt个， cnt对k整除，获取一共能循环多少圈
2, 获取head之后的k个节点，并保存为end，保存next节点，将end的next置为nullptr
3，reverse head-end
4，temp->next = reverse之后的结果，
5，temp指向末尾
6，循环。
*/
class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    /*
      旋转begin到end
    */
    ListNode * reverse(ListNode *begin) {
        if (!begin) {
            return begin;
        }
        ListNode *pre = nullptr, *curr = begin;
        while(curr) {
            ListNode *next = curr->next;
            curr->next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }
    
    // 统计个数
    int calListCnt(ListNode* head) {
        ListNode *root = head;
        int cnt = 0;
        while(root) {
            cnt++;
            root = root->next;
        }
        return cnt;
    }
    ListNode *getEnd(ListNode* head, int k) {
        ListNode *root = head;
        while(--k) {
            root = root->next;
        }
        return root;
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (!head) {
            return head;
        }
        if (k == 1) {
            return head;
        }
        int cnt = calListCnt (head);
        int circle = cnt / k;
        
        if (circle == 0) {
            return head;
        }
        
        ListNode *ret = new ListNode(-1);
        ListNode *temp = ret;
        ListNode *next, *start = head;
        
        while(circle--) {
            // 获取head之后的k个节点
            ListNode *end = getEnd(start, k);
            // 保存end的next
            next = end->next;
            // 切断关系
            end->next = nullptr;
            // reverse head 和 end
            ListNode * rev = reverse(start);
            // 开始拼接
            temp->next = rev;
            int tempNum = k;
            while(tempNum--) {
                temp = temp->next;
            }
            // 重新定义开始
            start = next;
        }
        
        temp->next = next;

        return ret ->next;
    }
};