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

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

这道题目考察的是链表的翻转和节点交换，需要注意链表的连接和指针的移动。

题目解答方法的文字分析

我们可以使用循环的方式来实现链表的分组翻转。对于每一组长度为 k 的节点，我们需要找到这一组的前一个节点 prev 和后一个节点 next，然后反转这一组的节点。

具体步骤如下：

1. 初始化一个虚拟头节点 dummy，并将其连接到链表的头节点 head。
2. 创建一个指针 prev，初始时指向虚拟头节点 dummy，用于定位当前要反转的一组节点的前一个节点。
3. 创建两个指针 start 和 end，分别指向当前要反转的一组节点的第一个节点和最后一个节点。
4. 使用循环将指针 end 移动到当前要反转的一组节点的最后一个节点。
5. 创建一个指针 next，初始时指向当前要反转的一组节点的后一个节点，用于后续连接。
6. 反转从 start 到 end 的一组节点，并同时更新指针 prev、start 和 end。
7. 最后，将指针 prev 连接到反转后的一组节点的第一个节点 end，将指针 start 连接到指针 next。
8. 继续循环，重复上述步骤，直到完成整个链表的分组翻转。

本题解析所用的编程语言

C++

完整且正确的编程代码

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode(-1); // 创建一个虚拟头节点
        dummy->next = head; // 将虚拟头节点连接到原链表头部
        ListNode* prev = dummy; // prev 指针，用于定位当前要反转的一组节点的前一个节点
        
        while (head) {
            ListNode* start = head; // 当前要反转的一组节点的第一个节点
            ListNode* end = start; // 当前要反转的一组节点的最后一个节点
            
            // 移动 end 指针到当前要反转的一组节点的最后一个节点
            for (int i = 1; i < k && end; ++i) {
                end = end->next;
            }
            
            if (!end) {
                break; // 如果不足 k 个节点，则不进行反转
            }
            
            ListNode* next = end->next; // 当前要反转的一组节点的后一个节点
            
            // 反转从 start 到 end 的一组节点
            while (start != end) {
                ListNode* temp = start->next;
                start->next = end->next;
                end->next = start;
                start = temp;
            }
            
            // 将 prev 连接到反转后的一组节点的第一个节点
            prev->next = end;
            prev = head; // 更新 prev 指针，用于连接下一组反转的节点
            head = next; // 更新 head 指针，用于遍历下一组反转的节点
        }
        
        return dummy->next; // 返回新链表的头节点
    }
};

这个代码使用循环的方式来实现链表的分组翻转。通过找到每一组的前一个节点 prev 和后一个节点 next，然后反转这一组的节点。最后，更新连接关系，得到分组翻转后的链表。

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！