K 个一组反转链表：迭代解法详解

K 个一组翻转链表（迭代解法）

K 个一组翻转链表 是链表操作类算法题中的经典进阶题，融合了「链表反转」的核心逻辑，并需处理分组、边界拼接等复杂场景。本文将从问题拆解、核心思路、代码解析、执行流程模拟四个维度，详解这道题的迭代解法。

问题描述

题目要求

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

• k 为正整数，且小于或等于链表长度。
• 若节点总数不是 k 的整数倍，最后剩余节点保持原有顺序。
• 不能只改变节点内部值，需实际进行节点交换。

示例

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

链表节点定义

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

核心思路拆解

核心是「分组反转 + 边界拼接」，拆解为 3 个关键步骤：

1. 统计链表长度：确定能分成多少个完整的 k 节点组；
2. 虚拟头节点兜底：用 dummy 节点统一 '首组反转' 和 '后续组反转' 的拼接逻辑；
3. 分组反转 + 拼接：对每一组 k 个节点执行「链表反转」，并将反转后的组与前一组、后一组正确拼接。

完整代码

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 步骤 1：统计链表总长度
        int n = 0;
        for (ListNode cur = head; cur != null; cur = cur.next) {
            n++;
        }
        // 步骤 2：创建虚拟头节点
        ListNode dummy = new ListNode(0, head);
        // p0：每一组待反转节点的「前驱节点」
        ListNode p0 = dummy;
        // pre/cur：链表反转的经典双指针
        ListNode pre = null;
        ListNode cur = head;
        // 步骤 3：遍历处理每一个 k 组
        for (; n >= k; n -= k) {
            // 步骤 4：反转当前 k 个节点
            for (int i = 0; i < k; i++) {
                ListNode nxt = cur.next;
                cur.next = pre;
                pre = cur;
                cur = nxt;
            }
            // 步骤 5：拼接反转后的组
            ListNode nxt = p0.next;
            p0.next.next = cur;
            p0.next = pre;
            p0 = nxt;
        }
        // 步骤 6：返回新头节点
        return dummy.next;
    }
}

逐行代码解析

1. 统计链表长度

计算链表总节点数 n，通过 n >= k 判断是否需要反转当前组。时间复杂度 O(n)。

2. 初始化核心指针

指针	初始值	核心作用
dummy	指向原头节点	避免单独处理第一组反转后头节点变更的问题
p0	指向 dummy	每一组待反转节点的前驱节点，负责拼接
pre	null	链表反转的'前一个节点'
cur	原头节点 head	链表反转的'当前节点'

3. 分组反转的外层循环

循环条件 n >= k 表示剩余节点数足够组成一个 k 组，才执行反转；每处理完一组，剩余节点数减少 k。

4. 反转当前 k 个节点

标准的'原地反转链表'，循环 k 次仅反转当前组的 k 个节点。nxt 必须提前保存 cur.next，否则丢失后续节点。

5. 拼接反转后的组

这 4 行是整个代码的核心难点：

1. ListNode nxt = p0.next：保存当前组反转前的头节点（反转后变成组尾）；
2. p0.next.next = cur：让反转后的组尾指向下一组的头；
3. p0.next = pre：让前驱节点 p0 指向反转后的组头；
4. p0 = nxt：更新 p0 为当前组的组尾，作为下一组的前驱。

6. 返回结果

无论第一组是否反转，dummy.next 始终指向最终链表的头节点。

执行流程模拟

以 head=[1,2,3,4,5], k=2 为例：

步骤	指针状态	链表状态
初始状态	n=5, dummy→1→2→3→4→5	dummy→1→2→3→4→5
第一组反转	反转后 pre=2, cur=3	1←2 3→4→5
第一组拼接	nxt=1, 1→3, dummy→2, p0=1	dummy→2→1→3→4→5
第二组反转	反转后 pre=4, cur=5	3←4 5
第二组拼接	nxt=3, 3→5, 1→4, p0=3	dummy→2→1→4→3→5
循环结束	n=1 < 2，剩余节点 5 不处理	dummy→2→1→4→3→5
返回结果	dummy.next=2	2→1→4→3→5

注意事项

1. 拼接时的指针顺序：必须先保存 p0.next，再修改 p0.next.next，最后修改 p0.next；
2. p0 的更新时机：只有拼接完成后，才能把 p0 设为当前组的组尾；
3. 剩余节点处理：通过 n >= k 控制循环，确保最后不足 k 个的节点不反转；
4. 虚拟头节点的必要性：如果没有 dummy，第一组反转后需要单独修改 head。

总结

1. 核心逻辑：统计长度→分组反转→拼接边界；
2. 关键指针：p0（组前驱）、pre/cur（组内反转）、dummy（统一头节点）；
3. 执行顺序：先反转组内节点，再拼接组的首尾，最后更新 p0 处理下一组。