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

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* reverse(ListNode* first, ListNode* last) //用于将k个链表进行翻转
    {   //first为表头，last为最后一个链表的next
        if(nullptr == first)
            return nullptr;
        ListNode *pPre = NULL;
        ListNode *pNode = first;
        ListNode *pCur = first->next;
        pNode->next = pPre;
        while(last != pCur)
        {
            pPre = pNode;
            pNode = pCur;
            pCur = pCur->next;
            pNode->next = pPre;
        }
        return pNode;//返回值是K链表的新头部
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(nullptr == head || k <= 0)
            return nullptr;
        ListNode *node = head;
        ListNode *NewHead = head;//新链表的头部，第一个翻转链表的头部
        ListNode *first = head;
        bool isHead = true;
        bool isbreak = false;
        while(1)
        {
            ListNode *newfirst = node;
            for(int i = 0;i < k;i ++)
            {
                if(!node)
                {
                    isbreak = true;
                    break;
                }
                node = node->next;
            }
            if(isbreak)
                break;
            ListNode *newLast = node;
            ListNode *NewNode = reverse(newfirst, newLast);
            if(isHead)//如果是第一个翻转的K链表，赋值新链表头部
            {
                NewHead = NewNode;  
                isHead = false;
            }
            else
            {
                first->next = NewNode;//1->4
            }
            newfirst->next = node;//3->5
            first = newfirst;
        }
        return NewHead;
    }
};
class Solution {
public:
    /**
     *
     * @param head ListNode类
     * @param k int整型
     * @return ListNode类
     */
    //迭代方法
    ListNode* reverse(ListNode* first, ListNode* last)
    {
        if(nullptr == first)
            return nullptr;
        ListNode *pPre = NULL;
        ListNode *pNode = first;
        ListNode *pCur = first->next;
        pNode->next = pPre;
        while(last != pCur)
        {
            pPre = pNode;
            pNode = pCur;
            pCur = pCur->next;
            pNode->next = pPre;
        }
        return pNode;
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(nullptr == head || k <= 0)
            return nullptr;
        ListNode *node = head;
        for(int i = 0;i < k; i++)
        {
            if(!node)
                return head;
            node = node->next;
        }
        ListNode *NewHead = reverse(head, node);
        head->next = reverseKGroup(node, k);
        return NewHead;
    }
};