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

题目考察的知识点

链表的基本操作。能熟练掌握链表的操作。

题目分析

这道题大概可以概括为：给定k值，k个一组翻转链表，如若剩余数量不足k个则原样输出。

特殊情况：

1. 当k=5，即链表长度时，就转化为了反转链表。
2. 注意空链表和单元素链表的处理，因为题目备注有规定k值的范围所以不需要担心大于长度小于长度这些七七八八的。

大概流程：

指针变量有四个：cur和pre都是反转链表时常用的指针，分别代表前一个指针和当前指针，start和final指针是下一组起点和尾节点，用于翻转后的位置确认和每组之间的链表连接，后面根据分组数num循环来操作待反转的链表分组，注意当循环组数达到最后一组的时候，final尾节点就应该是start节点，因为3->4在翻转后4->3，3这个start指针位置就是final尾节点位置。这里需要加个if判断一下。

其它的细节请看代码块注释，很详细了。

编程语言和代码展示

编程语言c++，代码展示如下：

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <iostream>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param k int整型
     * @return ListNode类
     */
    ListNode* reverseSwap(ListNode* head, int k) {
        ListNode* cur = head;
        ListNode* pre = nullptr;
        ListNode* temp = nullptr;
        while (k) {
            temp = cur->next;//记住下个节点方便步进
            cur->next = pre;//后面节点指向前面
            pre = cur;
            cur = temp;
            k--;
        }
        return pre;//返回反转后的最后一个节点
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        //题目宗旨：k节点一组翻转
        //注意点1 如果节点数不是k的整数倍 则剩余节点保持原有顺序
        //注意点2 空或者1个节点返回原head
        if (head == nullptr || head->next == nullptr)return head; //注意点2
        ListNode* cur = head;
        ListNode* pre = head;
        ListNode* start = cur;
        ListNode* final = nullptr;
        int count = 0;//长度
        int num = 0;//组数
        int i = k;//循环变量 等于k 因为k不能变 用于循环控制
        while (cur != nullptr) {
            count++;
            cur = cur->next;
        }
        cur = head;//用cur遍历之后一定要重置指向为head
        if(count == k){//说明整个链表为一组翻转==反转链表
            return cur=reverseSwap(head,k);
        }
        num = count / k;
        bool hflag = false;//用于控制头节点获取首次翻转后的分组头节点控制锁变量
        while (num) {//要进行反转的组数
            i = k;//循环变量重置
            while (i) {
                start = start->next;
                i--;
            }//start保存下一个待反转数组的入口地址
            final = start;//开始寻找下一组的尾节点
            if (num != 1) {
                i = k - 1;
                while (i) {
                    final = final->next;
                    i--;
                }
            }
            cur = reverseSwap(cur, k); //2
            if (hflag == false) {
                head = cur;//连接反转后的链表分组
                hflag = true;
            }
            pre->next = final;//当前分组首节点指向下一组尾节点
            pre = start;
            cur = start;//cur步进为最新的待反转分组入口
            num--;
        }
        return head;
    }
};