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

这道题算是比较难的了，我感觉，反转链表中即用到了一个递归的思想，也用到了头插法和尾插法的基础，大体思路就是将这个问题看成一个递归问题，需要翻转k个一组的，假设一共有n个组，那么他的子任务就是翻转完n-1组，一直到最后那一组不足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||head->next==NULL) //空或者只有一个数字
            return head;
        ListNode* once = head;
        int i = 0 ;
        while(once)
        {
            i++;
            once = once->next;
        }
        free(once);
        if(i>=k)
        {
            int j = 0;
            ListNode* nt = head;
            while(j<k)
            {
                j++;
                nt = nt->next;
            }
            ListNode* reverse_node = reverseKGroup(nt,k);
            //反转head之后的k个，然后连上reverse_node
            int p = 0 ;
            ListNode* newhead = new ListNode(-1);
            ListNode* once1 = head;
            while(p<k)
            {
                ListNode* cur = once1;
                once1 = once1->next;
                cur->next = NULL;
                if(p==0)
                {
                    newhead->next = cur;
                }
                else{
                    cur->next = newhead->next;
                    newhead->next = cur;
                }
                p++;
            }
            ListNode* oo = newhead;
            while(oo->next)
                oo = oo->next;
            oo->next = reverse_node;
            return newhead->next;        
        }
        else  //不足k的直接返回
            return head;
        
        
    }
};