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

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        if(head==null){
            return null;
        }
        // 通过函数计算链表长度
        int length=getLength(head);
        // 判断链表是否小于k，小于k不需要进行翻转
        if(length<k){
            return head;
        }
        // 否则声明指针用于记录翻转过程
        ListNode pre=null;
        ListNode cur=head;
        // 声明一个计数器
        int index=0;

        // 翻转前k个节点
        while(index<k){
            ListNode next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
            index++;
        }

        //递归翻转剩余节点
        head.next=reverseKGroup(cur,k);
        return pre;
    }
    private int getLength(ListNode head){
        int length=0;
        while(head!=null){
            length++;
            head=head.next;
        }
        return length;
    }
}

解题语言：java

本题的知识点：链表的翻转，递归，链表的遍历

思路如下：

首先，判断给定的链表是否为空。如果为空，直接返回null。

接下来，计算链表的长度。使用一个辅助函数getLength()，通过遍历链表来统计节点的数量。

然后，判断链表的长度是否小于k。如果小于k，说明不需要进行翻转，直接返回头节点head。

否则，声明一个指针pre和cur，用于记录翻转的过程。初始化pre为null，cur为头节点head。同时，声明一个计数器index，初始值为0。

在while循环中，翻转前k个节点。每次循环中，将cur指向的节点的下一个节点保存为next，然后将cur指向的节点的next指向pre，更新pre为cur，cur为next，计数器index自增1。

当翻转结束后，head指向当前翻转的链表段的尾节点，pre指向当前翻转的链表段的头节点。将head.next指向递归调用reverseKGroup()返回的结果，即翻转剩余部分链表，并将翻转后的链表段的头节点pre返回。

最后，返回pre，即整个链表翻转后的结果。

整体思路就是利用递归和迭代的方式，先翻转前k个节点，然后递归处理剩余的节点，再将各个翻转后的链表段连接起来。这样就实现了将链表按照每k个节点进行翻转的功能。

时间复杂度分析：

遍历一次链表来计算链表的长度的时间复杂度为O(n)，其中n是链表的长度。

翻转过程中需要遍历k个节点，所以时间复杂度为O(k)。

递归调用reverseKGroup函数的次数最多为n/k次，其中n/k是链表的长度除以k的整数部分。

整体的时间复杂度为O(n)，具有很好的时间效率。