🔗 K 个一组翻转链表

题目来源：25. K 个一组翻转链表 – 力扣（LeetCode）

📌 题目描述

给你链表的头节点 head，每 k 个节点一组进行翻转，请你返回修改后的链表。

要求：

• k 是一个正整数，且 k <= 链表长度
• 如果节点总数不是 k 的整数倍，最后剩余的节点保持原有顺序
• 不能只改变节点内部的值，必须实际交换节点（指针重连）

✅ 示例解析

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
解释：前两组 [1,2] → [2,1]，[3,4] → [4,3]，剩余 [5] 不足 k=2，保持原序。

示例 2：

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
解释：第一组 [1,2,3] → [3,2,1]，剩余 [4,5] 不足 k=3，保持原序。

⚠️ 提示

• 链表中的节点数目为 n
• 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000

💡 解法：分组反转 + 虚拟头节点 —— O(n) 时间，O(1) 空间

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode end = dummy;

        while (end != null) {
            // 1. 定位当前组的尾节点 end
            for (int i = 0; i < k && end != null; i++) {
                end = end.next;
            }
            if (end == null) break; // 不足 k 个，结束

            // 2. 保存下一组的起点
            ListNode nextGroupStart = end.next;
            end.next = null; // 临时断开，便于反转

            // 3. 反转当前组 [start ... end]
            ListNode start = pre.next;
            pre.next = reverse(start); // 接上反转后的头

            // 4. 将原组头（现组尾）连到下一组
            start.next = nextGroupStart;

            // 5. 更新 pre 和 end，准备下一轮
            pre = start;
            end = start;
        }

        return dummy.next;
    }

    // 反转链表，返回新头节点
    public ListNode reverse(ListNode head) {
        ListNode p = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = p;
            p = head;
            head = next;
        }
        return p;
    }
}

📊 复杂度分析

• 时间复杂度：O(n)
  • 每个节点最多被访问两次（一次定位 end，一次反转），总体线性。
• 空间复杂度：O(1) ✅
  • 仅使用常数指针变量，无递归栈（若递归反转则空间为 O(k)）。

🧩 解题思路

核心思想：分组切割 + 局部反转 + 重新拼接

1. 初始化：
   • 创建虚拟头节点 dummy，指向 head。
   • pre 指向当前组的前驱节点（初始为 dummy）。
   • end 用于定位当前组的尾节点（初始也为 dummy）。
2. 循环处理每组： a. 定位组尾：
   • end 从当前位置前进 k 步。
   • 若中途 end == null → 说明不足 k 个 → 直接退出。
   b. 断开当前组：
   • 保存 nextGroupStart = end.next（下一组起点）。
   • end.next = null → 临时断开当前组，便于独立反转。
   c. 反转当前组：
   • start = pre.next（当前组头）
   • pre.next = reverse(start) → 将反转后的新头接回主链。
   d. 拼接下一组：
   • 原来的 start 节点（现在是组尾） → start.next = nextGroupStart
   e. 更新指针：
   • pre = start（当前组尾成为下一组的前驱）
   • end = start（同步位置，准备下一轮前进）
3. 返回：
   • dummy.next 为最终链表头。

举例说明：

输入：head = [1,2,3,4,5], k = 2

初始：dummy → 1 → 2 → 3 → 4 → 5
       pre^  end^

第1轮：
end 前进2步 → end 指向 2
断开：2.next = null → [1→2] 与 [3→4→5] 分离
反转 [1→2] → [2→1]
pre.next = 2 → dummy→2→1
1.next = 3 → 1→3→4→5
更新：pre = 1, end = 1

当前：dummy → 2 → 1 → 3 → 4 → 5
                   pre^ end^

第2轮：
end 前进2步 → end 指向 4
断开：4.next = null → [3→4] 与 [5] 分离
反转 [3→4] → [4→3]
pre.next = 4 → 1→4→3
3.next = 5 → 3→5
更新：pre = 3, end = 3

当前：dummy → 2 → 1 → 4 → 3 → 5
                           pre^ end^

第3轮：
end 前进2步：第一步 end=5，第二步 end=null → break

最终：[2,1,4,3,5] ✅

边界处理：

• k = 1 → 每个节点自成一组 → 反转后不变 → 原链表返回。
• k = n → 整个链表反转。
• 最后一组不足 k → 不进入反转逻辑 → 自然保持原序。
• 空链表或单节点 → 安全处理，不进入循环或直接返回。