剑指Offer 链表中的节点每k个一组翻转 C++实现

题目描述
将给出的链表中的节点每k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。
要求空间复杂度 \ O(1) O(1)
例如：
给定的链表是1→2→3→4→5
对于k=2, 你应该返回 2→1→4→3→5
对于k=3, 你应该返回 3→2→1→4→5

解法
若当前小块的个数不小于k，则每小块中使用头插法倒置该块，那么当前需要5个指针，nhead当前块的头指针，ntail当前块的尾指针，cur待插入结点指针，nt待插入结点下一个结点指针，ptail上一块的尾指针，当前块倒置完后，要连接上一块与当前块。
注意：
1、要先处理第一块
2、然后，cur指向每一块的头结点，也是这一块的尾结点，此时要将ntail->next置空。
3、当前块倒置完，要与上一块相连接 ptail->next = nhead;

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        // 特殊情况，头结点为空或者头结点下一指针为空
        if(head == NULL || head->next == NULL) return head;
        
        ListNode *nhead, *cur, *nt, *ptail, *ntail;
        ListNode * count; //计数指针
        int i;
        
        //先处理第一小块
        cur = head;
        ntail = cur;
        nhead = cur;
        i = 0;
        count = cur;
        while(i < k && count != NULL)
        {
            count = count->next;
            i++;
        }
        //第一小块的个数不小于k，则调整结点顺序
        if(i < k) return head;
        else
        {
            cur = nhead->next;
            ntail->next = NULL; //这一步非常重要，不然链表会成环
            for(i = 0; i < k - 1; i++)
            {
                nt = cur->next;
                cur->next = nhead;
                nhead = cur;
                cur = nt;
            }
            head = nhead; //将链表头指针指向第一块处理后的第一个结点
        }
        
        while(cur != NULL)
        {
            //处理剩下的块,上一块的尾指针
            ptail = ntail;
            
            //跳至当前块的处理,cur初始指向当前块的第一个结点
            nhead = cur;
            ntail = cur;
            //判断该块是否节点数小于k
            i = 0;
            count = cur;
            while(i < k && count != NULL)
            {
                count = count->next;
                i++;
            }
            if(i < k)
            {
                ptail->next = nhead;
                return head;
            }
            else
            {
                //块内的处理
                cur = nhead->next;
                ntail->next = NULL;
                for(i = 0; i < k - 1; i++)
                {
                    nt = cur->next;
                    cur->next = nhead;
                    nhead = cur;
                    cur = nt;
                }
                ptail->next = nhead;//连接当前块与上一块
            }
        }
       
        return head;
    }
};

时间复杂度O(n)
空间复杂度O(1)