题解 | 链表中的节点每k个一组翻转

import java.util.*;

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

public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        //防止空链表，单链表，k=1
        if (head == null || head.next == null || k == 1) return head;

        // dummy 方便处理从头开始的第一组
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        // 1) 计算长度
        int length = 0;
        ListNode p = head;
        while (p != null){
            length++;
            p = p.next;
        }

        // 2) 分组处理，groupPre 指向每组的前驱
        ListNode groupPre = dummy;
        ListNode cur = head;

        for (int i = 0; i < length / k; i++) {
            // 组内做 k-1 次“头插法”
            // 目标：把 cur 后面的节点一个个抠出来，插到 groupPre 后面
            for (int j = 1; j < k; j++) {
                ListNode next = cur.next;        // 待搬节点
                cur.next = next.next;            // 从原位置摘掉 next
                next.next = groupPre.next;      // 插到组头前（即 groupPrev 后面）
                groupPre.next = next;           // 组新头更新为 next
            }
            // 组完成：cur 变成这组尾，groupPre 前移到组尾
            groupPre = cur;
            cur = cur.next; // 下一组的起点
        }
        return dummy.next;
    }
}