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

考察的知识点：与链表有关的题基本都是插入，删除，交换顺序等，解决这些问题通常将链表的指针进行修改。

问题分析： 使用虚拟头节点的技巧，可以避免对头节点复杂的分类考虑，简化操作。

1. 创建虚拟节点dummy,dummy.next = head;
2. 计算总长度,判断需要反转几个分组.
3. 反转时将指针按步骤修改即可,可参考代码以及下图

本题解析所用的编程语言：java

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) {
        // write code here
        if (head==null || k <= 1) {
            return head;
        }

        // 统计链表长度
        int length = 0;
        ListNode node = head;
        while (node!=null) {
            ++length;
            node = node.next;
        }
        // 使用虚拟头节点来简化操作
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode prev = dummy;
        ListNode curr = head;
        
        int count = length / k;
        for (int i = 0; i < count; 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;
    }
}