题解 | #链表中的节点每k个一组翻转#

• 思路： 跟上一个类似，区间反转。这个较麻烦的是找循环的两个端点，进行连接； 例如； 1 2 3 4 5 ， 2； 第一次循环， 1 与 2 ， 考虑右端点即可； 2 1 3 4 5； 第二次循环， 3 与 4， 要考虑左右两个端点， 让 1 -> 4; 3 -> 5;

```/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode* reverseKGroup(struct ListNode* head, int k ) {
    // write code here
    struct ListNode *CyclicPrefix, *LoopSuffix, *TraverseHead, *Prefix, *Suffix;
    // 声明了五个变量，分别是：循环前的一个结点的地址， 一个循环之后的结点的地址，一个负责遍历结点地址的指针； 复杂了我， 就是连接点；
    // 一个循环的第一个结点的指针，一个循环的最后一个的结点的指针
    // 刚开始要遍历从第一个结点到第K个结点，cyclicPrefix == Prefix == head;
    // 第一步：查找元素个数；
    TraverseHead = head;
    int count = 0;
    while(TraverseHead) {
        TraverseHead = TraverseHead->next;
        count++;
    }
    if(count == 0 || k > count) return head; // 如果为空链表或k > 节点数；返回 head; 即结束；
    if(k == 1) return head; // 循环一次，那不就是无循环嘛；
    int m = count/k; // 循环次数；
    m--; // 减去首次反转；
    // 首先，反转 1 to k的，由于cyclicPrefix == Prefix == head，所以不能跟之后的反转区间操作一样；
    struct ListNode *q, *p; // 反转后的头指针 和 一个遍历地址；
    Suffix = head; // 因为第一次循环完后，head 的结点就移到了循环内最后一个了，所以内循环最后一个为head；
    for(int i = 0; i < k; i++) {
        q = head;
        head = head->next;
        q->next = p;
        p = q;
    }
    CyclicPrefix = head;// 下一个循环的第一个值；
    Suffix->next = CyclicPrefix; // 内循环的追后一个结点的指针域指向外循环的第一个结点； 
    Prefix = CyclicPrefix;
    CyclicPrefix = Suffix;//，重置CyclicPrefix, LoopSuffix;
    head = p; // 将头指针p赋值给head；
    // 首次循环结束；
       
    struct ListNode *TempSuffix, *TempLoopSuffix, *TempPrefix;// 临时存储下一次的中间量；
    while(m--) // 循环；
    {
       q = Prefix; TempPrefix = Prefix;// 从Prefix 开始遍历；
        for(int i = 0; i < k-1; i++) {
            q = Prefix;
            Prefix = Prefix->next;
            q->next = p;
            p = q;
        }
        TempSuffix = Prefix; // TempSuffix == Suffix； 找左端点之前的
        q = Prefix; Prefix = Prefix->next;
        q->next = p; p = q;
        TempLoopSuffix = Prefix; // TempLoopSuffix == LoopSuffix; 找右端点之后一个的端点
        CyclicPrefix->next = p; // 衔接 上一个左端点之前的跟本次循环的左端点连接
        TempPrefix->next = TempLoopSuffix; //衔接 上一个右端点之前的跟本次循环的右端点之后的相连接；
        CyclicPrefix = TempPrefix; // 重置外循环的第一个：
        Prefix = TempLoopSuffix; // 内循环第一个；
        // 好像没有用上Suffix LoopSuffix;， 我用Temp...给代替了，因为那样不太好理解；
        
    }
    return head;
}