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

考察的知识点：遍历链表、修改节点的指针指向；

解答方法分析：

1. 首先，检查给定的头节点是否为空或 k 的值是否小于等于 1，如果是，直接返回原链表。
2. 统计链表的长度，可以通过遍历链表，每遍历一个节点长度加一来实现。
3. 创建一个虚拟头节点(dummy)，指向原链表的头节点。
4. 定义两个指针(prev 和 curr)，初始时分别指向虚拟头节点(dummy)和原链表的头节点。
5. 使用两层循环，外层循环控制分组的数量，内层循环控制每组内节点的反转。
6. 在内层循环中，每次将 curr 的下一个节点移动到 prev 的下一个位置，同时将该节点的下一个指针指向 prev 的下一个位置，并将 prev 的下一个指针指向该节点。重复 k-1 次，完成当前组内节点的反转。
7. 更新 prev 和 curr 的指向，使其指向下一组的起始位置和下一组的第一个节点。
8. 返回虚拟头节点(dummy)的下一个节点，即为反转后的链表头节点。

所用编程语言：C++；

完整编程代码：↓

/**
 * 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 length = 0;
        ListNode* node = head;
        while (node != nullptr) {
            length++;
            node = node->next;
        }

        // 使用虚拟头节点来简化操作
        ListNode* dummy = new ListNode(0);
        dummy->next = head;

        ListNode* prev = dummy;
        ListNode* curr = head;

        for (int i = 0; i < length / k; i++) {
            for (int j = 1; j < k; j++) {
                ListNode* next = curr->next;
                curr->next = next->next;
                next->next = prev->next;
                prev->next = next;
            }
            prev = curr;
            curr = prev->next;
        }

        return dummy->next;
    }
};