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

采用fast、slow快慢指针来进行分组，对每个分组使用头插法对链表进行翻转。使用curr_group_tail来记录当前组的尾部，即采用头插法时该节点为分组的首节点。进行到下一组时，curr_group_tail即是新链表的尾部。若剩下的节点不够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
        ListNode* new_head=NULL;
        ListNode* new_tail=NULL;
        ListNode* fast = head;
        ListNode* slow = head;
        ListNode* group_head = NULL;
        while(fast)
        {
            group_head = NULL;
            //快指针先移动k个位置去占位;
            int group = k;
            while(group>0)
            {
                if(fast == NULL)
                    break;
                fast = fast->next;
                group--;
            }
            //当前组的尾部，在下一个时记录成新链表的尾部;
            ListNode* curr_group_tail = NULL;
            if(group==0)
            {
                //够k个位置;
                ListNode* tmp = NULL;
                while(slow && slow!=fast)
                {
                    tmp = slow->next;
                    //采用头插法;
                    if(group_head == NULL)
                    {
                        group_head = slow;
                        slow->next = NULL;
                        curr_group_tail = group_head;
                    }else{
                        slow->next = group_head;
                        group_head = slow;
                    }
                    slow = tmp;
                }

                if(!new_head)
                {
                    new_head = group_head;
                }else
                {
                    new_tail->next = group_head;
                }
                //更新新链表的尾部为当前分组的尾部;
                new_tail = curr_group_tail;
            }else
            {
                //没有k个节点时，直接链接到新链表中;
                if(!new_head)
                {
                    new_head = slow;
                }else
                {
                    new_tail->next = slow;
                }
                break;
            }
        }
        return new_head;
    }
};