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

知识点：

1. 单链表的遍历与操作。
2. 分组翻转链表。
3. 使用哑节点（dummy node）简化链表操作。

题意分析：

题目描述了一个链表，表示农场里的牛，节点的值为牛的编号。农场主想要重新分组牛群，要求每k个节点一组进行翻转。如果节点总数不是k的整数倍，最后剩余的节点保持原有顺序。要求返回修改后的牛群链表。

时间复杂度：

假设链表中有N个节点。

1. 在代码中，我们需要对链表进行分组翻转。在每个分组翻转的过程中，涉及到反转k个节点的操作，需要O(k)的时间复杂度。而整个链表共有N/k个分组。
2. 因此，总的时间复杂度为O(N)。

代码分析：

代码中的解决思路是使用快慢指针进行链表分组，然后将每个分组进行翻转，并连接到前一个分组和后一个分组。具体的步骤如下：

1. 如果链表为空或k<=1，不需要翻转，直接返回原链表。
2. 创建一个前置头节点dummy，方便处理边界情况。
3. 初始化prev指针指向dummy，curr指针指向链表头节点。
4. 开始循环遍历链表： a. 定位当前分组的头节点为groupHead，调用getTail方法获取当前分组的尾节点为tail。 b. 如果剩余节点数量不足k个，不进行翻转，直接结束循环。 c. 将当前分组从链表中截断，即将tail.next置为null。 d. 调用reverse方法翻转当前分组。 e. 将翻转后的分组连接到前一个分组的后面，将翻转后的头节点连接到下一个分组的前面。 f. 更新prev指针为当前分组的尾节点，更新curr指针为下一个分组的头节点。
5. 返回翻转后的链表头节点，即dummy.next。

代码：

import java.util.*;

class ListNode {
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}

public class Solution {
    /**
     * 将链表每K个节点一组进行翻转
     *
     * @param head ListNode类 链表的头节点
     * @param k int整型 每组节点个数
     * @return ListNode类 翻转后的链表头节点
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        // 如果链表为空或k<=1，不需要翻转，直接返回原链表
        if (head == null || k <= 1) {
            return head;
        }

        ListNode dummy = new ListNode(-1); // 创建一个前置头节点，方便处理边界情况
        dummy.next = head;

        ListNode prev = dummy; // prev指针指向当前翻转组的前一个节点
        ListNode curr = head;  // curr指针指向当前翻转组的第一个节点

        while (true) {
            ListNode groupHead = curr; // groupHead指针指向当前翻转组的头节点
            ListNode tail = getTail(curr, k); // 获取当前翻转组的尾节点

            if (tail == null) {
                break; // 如果剩余节点数量不足K个，不进行翻转，直接结束
            }

            ListNode nextGroupHead = tail.next; // nextGroupHead指向下一个翻转组的头节点
            tail.next = null; // 将当前翻转组的尾节点的next指针置为null，以便翻转

            reverse(groupHead); // 翻转当前翻转组

            prev.next = tail; // 将翻转后的尾节点连接到前一个翻转组的后面
            groupHead.next = nextGroupHead; // 将翻转后的头节点连接到下一个翻转组的前面

            prev = groupHead; // prev指针指向当前翻转组的尾节点
            curr = nextGroupHead; // curr指针指向下一个翻转组的头节点
        }

        return dummy.next; // 返回翻转后的链表头节点
    }

    // 获取从当前节点开始的第K个节点，如果不足K个节点则返回null
    private ListNode getTail(ListNode head, int k) {
        for (int i = 1; i < k; i++) {
            if (head == null) {
                return null;
            }
            head = head.next;
        }

        return head;
    }

    // 翻转以head为头节点的链表
    private void reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
    }
}