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

/*
看这蛮长的，其实思路还是很简单的，他要求O(1)的空间复杂度，但是用到了队列，先说思路吧
求链表长度，除于k,看组的个数，将每一组分成一个子链表，对子链表求逆序，然后返回头节点，
然后上一组的尾节点指向返回的头节点，这里调用逆序之前得记录最后一组最后一个得下一个，是
为了逆序好所有的组之后为节点连上刚刚的记录的节点，这里用队列是因为下一组得头节点不好记录
干脆用链表在开始遍历时记录下来
*/
#include <queue>
#include <stack>
class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* reverseKChildGroup(ListNode* head,int k)
    {
        ListNode *pre = nullptr;
        ListNode *mid = head;
        ListNode *next = mid->next;
        int num = k-1; 
        while(num--)
        {
            mid->next = pre;
            pre = mid;
            mid = next;
            next = next->next;
        }
        mid->next = pre;
        return mid;
    }
    ListNode* reverseKGroup(ListNode* head, int k) 
    {
        if(!head||!head->next||k<=1) return head;
        int size = 0;//节点个数
        ListNode *ptail;
        ListNode *pNode = head;
        ListNode *ptemp = head;
        queue<ListNode*>que;
        int t = 0;
        while (pNode)
        {
            t++;
            size++;
            pNode = pNode->next;
            if(k == t)
            {
                que.push(pNode);
                t=0;
            }
        }
        if(k>size) return head;
        pNode = head;
        int Index = 0;
        while(Index<((size/k)*k))
        {
            Index++;
            ptemp=ptemp->next;  
        }
        for(int i = 0;i<(size/k);i++)
        {
            if(i==0)
            {
                head = reverseKChildGroup(pNode, k);
                ptail = head;
            }
            else 
            {
                int j = k-1;
                while(j--)
                {
                    ptail = ptail->next;
                }
                ptail->next = reverseKChildGroup(que.front(), k);
                ptail=ptail->next;
                que.pop();
            }
        }
        if(ptemp)
        {
            int j = k-1;
            while(j--)
            {
                ptail = ptail->next;
            }
            ptail->next = ptemp;
        }
        return head;
    }
};