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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(head==nullptr||k==1)
        {
            return head;
        }
        int num=0;
        ListNode* p=head;
        while(p!=nullptr)
        {
            ++num;
            p=p->next;
        }
        int group = num/k;
        ListNode* dynode=new ListNode(-1);
        dynode->next=head;
        int counterk=1;
        ListNode* pre=dynode;
        ListNode* pnext=nullptr;
        ListNode* end=nullptr;
        ListNode* start=nullptr;
        for(int i=0;i<group;i++)
        {
            start=pre->next;
            end=start;
            for(int i=1;i<k;i++)
            {
                end=end->next;
            }
            pnext=end->next;
            //断开
            end->next=nullptr;
            //反转
            reverselist(start);
            //重连
            pre->next=end;
            start->next=pnext;
            pre=start;
        }
        head=dynode->next;
        return head;
    }
private:void reverselist(ListNode* head)
{
    ListNode* pre=nullptr;
    ListNode* cur=head;
    ListNode* pnext=nullptr;
    while(cur!=nullptr)
    {
        pnext=cur->next;
        cur->next=pre;
        pre=cur;
        cur=pnext;
    }
}
};

首先要找到有多少组需要翻转，然后每一组翻转都要确定好它的前一个位置、开始位置、结束位置、下一个位置，这样每k个翻转时，数据能够及时更新，第一组的前一个位置就是头结点，开始位置是第一个，结束位置是第k个，下一个位置是k+1个，第二组的前一个位置是第一组翻转完成以后得最后一个，也就是翻转之前的开始位置，开始位置是翻转之前的下一个位置，结束位置为后面第k个位置。在翻转之前要先断开，断开之前要保留好当前这一组的下一个位置，以便后续更新。断开并翻转以后，要将翻转之后的结果连接到下一个位置，以便再次翻转。因为只翻转k的整数倍组，所以最后一组翻转完成以后连接上了剩余的不满足k个数据中第一个。