题解 | #牛群的重新分组#

考察的知识点：与链表有关的题基本都是插入，删除，交换顺序等，解决这些问题通常将链表的指针进行修改。

问题分析： 这道题需要改变头结点，所以新建一个头结点，然后需要翻转单链表，翻转单链表可以用链表头插， 将需要翻转的结点一个一个头插到某个结点的后面，总之，这道题用头插不是很容易。下面代码看看就行，别细看。

本题解析所用的编程语言：c++

代码如下：

int isreverse(ListNode*& tmp, int& k) //判断是否翻转
{
    int n = 0;
    while (tmp)
    {
        ++n;
        if (n == k)
        {
            if (tmp->next == nullptr) //因为如果最后一个结点头插，最后一个结点的指针将头插到前一个，此时tmp后面就不为空，所以这里附空
            {
                tmp = nullptr;
            }
            return 1;
        }
        tmp = tmp->next;
    }
    return 0;
}
ListNode* reverseKGroup(ListNode* head, int k)
{
    // write code here
    ListNode* newhead = new ListNode(-1);
    newhead->next = head;
    ListNode* prev = newhead; //prev是开始进行翻转的前一个结点
    ListNode* end = prev->next; //end是每次头插第一个结点
    //头插k个结点
    ListNode* cur = prev->next; //当前节点
    ListNode* next = cur->next; //下一个结点
    while (cur)
    {
        ListNode* tmp = cur; //tmp进行遍历
        if (isreverse(tmp, k)) //够翻转，进行翻转
        {
            for (int i = 0; i < k; ++i)
            {
                if (i == 0)
                {
                    end = cur;
                }
                //头插
                cur->next = prev->next; 
                prev->next = cur;
                //更新结点
                cur = next;
                if (cur->next)
                    next = next->next;

            }
            //连接结点
            prev = end;
            end->next = cur;
        }
        else
            break;
        if (tmp == nullptr) //如果全部翻转，将最后一个结点指空，end是每次头插第一个结点，也就是最后一个结点
        {
            end->next = nullptr;
            break;
        }
    }

    head = newhead->next;
    delete(newhead);

    return head;
}