主要思路

因为是从上一题刷过来的，所以理所当然地沿用上一题的翻转思路。

首先因为上一题是m到n进行翻转，这一题相当于拆成了许多个m到n进行翻转，所以核心翻转部分可以直接抄。

首先想了想该怎么做：

想法一：先遍历一遍数出有多少个结点，然后再从头分块进行翻转

想法二：先根据k分块翻转，直到最后遇到不足k时再重新反转一遍，这样只走一遍就行

虽然两个都是O(n)，但感觉思路二需要遍历的次数更少，所以选思路二了。

情况讨论（假设有n个结点）：

特殊情况：

• k = 1，不反转
• head为空或者只有链表一个结点

正常情况：

• k >= n：不反转（或者反转2次）
• k < n：
• 能整除：直接返回头结点
• 不能整除：剩下部分再反转

缺点：当k=n时需要翻转2次

以k=3为例：

代码

class Solution {
  public:
    ListNode* reverseKGroup(ListNode* head, int k) {
		// 特殊情况特殊对待。  
		if (head == nullptr || 
			  head->next == nullptr ||
				  k == 1) 
			return head; 
        
        // 正常情况
        // 1. （初始化要用的变量）创建临时头结点并连接
        ListNode* tmp_head = new ListNode(-1);
        tmp_head->next = head;

        // 1.2 创建交换用的指针、计数
        // p:前面不动的指针，p指q的pre结点
	  	// q：指向“把前面的结点往p后面扔”的结点。
        ListNode* p = tmp_head, *q = head;
        ListNode* t = head->next; // 此时已经排除了head为空的情况
        // 用于for内计数，由于后面需要用到i，所以不放for里创建
	  	int i = 1; 
	  
	  	// 2. 开倒！
        while (q->next != nullptr) {
            for (i = 1; i < k && q->next != nullptr; i++) { // k个结点要做k-1次反转
                t = q->next;
                q->next = t->next;
                t->next = p->next;
                p->next = t;
            }

		  	// 往后跳一格，前往下一个组
            if (i == k && // 表示for循环完整结束
                    q->next != nullptr){ // 防止超内存
                p = q; // p移动到q的位置，因为p的前结点不会变
                q = q->next;
                // 这里不更新t，因为可能碰到null的情况，所以放到for里面就行了
            }
        }
	  
	  	// 3. 看看是否需要再翻转
        // 如果i=k，说明for循环正常结束了。反之就说明for循环没有正常结束
        if (i != k) { 
            // 先更新指针，让q回到p的下一结点，也就是t
            q = t;
            while (q->next != nullptr) { // 再走一遍流程，反转一遍
                t = q->next;
                q->next = t->next;
                t->next = p->next;
                p->next = t;
            }
        }
        return tmp_head->next;
    }
};