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

• 首先，题目有两个特殊输入，即空 或者k=1 该情况只需直接返回即可
• 下面考虑别的情况：

从第一个结点开始遍历

逆置的起点一定是从(n-1)k+1位 到 nk 如 123 k=3 逆置从1 到 3 n=1 

由于只有每次遇到k的倍数位时开始逆置,逆置个数为k个，而当出现不满k个的组就不会进行逆置

我们考虑创建一个空的头结点，每次遍历到倍数nk时开始逆置，但是同时需要记录逆置的开始指针，以及所需的指针 

例如： 12345 3 用q记录1 从1开始到3 用p记录3 r记录4 

q:用于记录每个开始逆置的结点

p:用于记录当前结点情况 为中间或逆置开始 或逆置结束结点

r:用于记录逆置结束位的下一位 ，方便下一次进行逆置

这里采用了i=1记录每个结点情况，是否为 首 中 尾

• 若i%k==1，则令q=到当前位置; 此情况代表p遍历到了第（n-1）k+1位
• 若i%k==0，p为当前位置 ,r为当前位置的下一位,并开始逆置; 此情况代表p遍历到了nk位
• 其余情况， p往后移动 

 逆置:

tempHead=p;  注意：逆置结束后 p为新的头结点

（当q不为r时）{//头插法

            temp=q->next;

            q->next=pre->next;

            pre->next=q;

            q=temp;

     }

     p=r;（回到i%k为1的情况 q=p;）

     pre=tempHead;

    当p为空时，要么结点全都接完了，要么位数不够，把剩余结点接入L即可

 位数不够时 (n-1)k+2 <= i <= nk 

    如果（i-1）%k!=0 这里取i-1去取余 

     pre->next = q; 接入头结点

struct ListNode* reverseKGroup(struct ListNode* head, int k ) {
    // write code here
    
    //特殊情况
    if(k <= 1 || head == NULL){
        return head;
    }
    
    int i = 1;
    //创建一个头结点,便于反转
    struct ListNode* L = (struct ListNode*)malloc(sizeof(struct ListNode));
    L->next = NULL;
    struct ListNode *p,*pre,*q,*r,*tempHead;
    struct ListNode *temp;
    pre = L; 
    p = head; 
    
    while(p){ 
       
        if(i % k == 1){
            q = p;
        }
        
        if(i % k == 0){
            //r指向 p 的下一个 temp 指向 q
            r = p->next;
            tempHead = q;
            //头插法
            while(q!=r){
                temp = q->next;
                q->next = pre->next;
                pre->next = q;
                q = temp;
            }
            p = r;
            pre = tempHead;
            
        }else{
            p = p->next;
        
        }
        i++;
    }
    
    if((i-1) % k != 0){
        pre->next = q;
    }

    return L->next;