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

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 || k == 1) {
                return head;
            }

            ListNode dummy = new ListNode(0);
            dummy.next = head;

            ListNode pre = dummy;
            ListNode end = dummy;

            while (end.next != null) {
                //  end 指针往前走 k 步
                for (int i = 0; i < k && end != null; i++) {
                    end = end.next;
                }

                // 如果 end 走到 null，说明剩余节点不足 k 个，保持原样，直接跳出循环
                if (end == null) {
                    break;
                }

                // 记录当前组的起点，以及下一组的起点
                ListNode start = pre.next;
                ListNode next = end.next;

                // 断开当前组与后面链表的联系，准备独立翻转
                end.next = null;

                //  翻转当前组，并让 pre 的 next 指向翻转后的新头节点（即原来的 end）
                pre.next = reverse(start);

                // 翻转后，start 变成了当前组的尾巴，让它和后面的链表连起来
                start.next = next;

                //  指针归位，准备进入下一组的循环
                pre = start;
                end = pre;
            }

            return dummy.next;
        }

        private ListNode reverse(ListNode head) {
            ListNode pre = null;
            ListNode curr = head;
            while (curr != null) {
                ListNode next = curr.next; // 先保存下一个节点
                curr.next = pre;           // 翻转指针指向
                pre = curr;                // pre 往前走
                curr = next;               // curr 往前走
            }
            return pre;
        }
}