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

本题要求反转k个一组的链表。使用递归函数可以简化思路，首先划分子问题，子问题是K个相同的部分。对于一个部分【a,b)反转函数很简单。剩下的我们应该同样调用反转函数，我们不必关心这个递归内部的压栈是什么样的，只需要关心这个函数就是用来反转的。因此a.next=reverserGroup(b.next,k)；链接起来即可。

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

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        if(head==NULL)return NULL;//递归的出口
        ListNode* a=head;
        ListNode* b=head;
        for(int i=0;i<k;i++){//找到b的位置
            if(b==NULL)return head;
            b=b->next;
        }
        ListNode* res=reverseN(a, b);//反转【a,b)区间段
        a->next=reverseKGroup(b, k);//调用递归
        return res;
        
        
    }
    ListNode * reverseN(ListNode* a,ListNode* b){//辅助函数反转[a,b)区间段的元素
         ListNode *pre,*cur,*nex;
         cur=nex=a;
        while(cur!=b){
            nex=cur->next;
            cur->next=pre;
            pre=cur;
            cur=nex;
        }
        return pre;
    }
};