25. K个一组翻转链表#

生活中的分组管理#

想象一个大型项目的场景：项目经理需要将100名员工分成每组10人的小组，每个小组负责不同的模块，而每个小组内部还要重新调整座位安排。这就像我们今天要讨论的K个一组翻转链表问题：我们需要将链表节点分成固定大小的组，并在每组内部进行翻转重组。

问题描述#

题目目标#

LeetCode第25题”K个一组翻转链表”要求：给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例 1#

输入： 1 → 2 → 3 → 4 → 5，k = 2 输出： 2 → 1 → 4 → 3 → 5 链表示意：

输入:  1 -> 2 -> 3 -> 4 -> 5 -> null
k = 2
输出:  2 -> 1 -> 4 -> 3 -> 5 -> null

text

说明： 每 k 个节点为一组翻转，不足 k 个的尾部节点保持原顺序。

示例 2#

输入： 1 → 2 → 3 → 4 → 5，k = 3 输出： 3 → 2 → 1 → 4 → 5 链表示意：

输入:  1 -> 2 -> 3 -> 4 -> 5 -> null
k = 3
输出:  3 -> 2 -> 1 -> 4 -> 5 -> null

text

说明： 每 k 个节点为一组翻转，不足 k 个的尾部节点保持原顺序。

补充说明#

链表题的输入本质上是节点之间的连接关系，重点通常是返回处理后的头节点或目标节点。

递归解法：项目分配的艺术#

就像一个睿智的项目经理，递归解法的优雅之处在于：我们只需要关注当前这一组的翻转，至于后面的组怎么翻转，交给”下属”（递归）去处理就好。等下属完成任务后，我们再将当前组和后续结果整合起来。

递归思路解析#

就像项目分配一样：

先检查手上有没有足够的人手（节点）可以组成一组
如果够一组，就处理这一组的内部调整（翻转）
将剩下的人交给下属继续分组处理
等下属处理完，再把当前组和下属处理好的结果连接起来

递归实现#

public ListNode reverseKGroup(ListNode head, int k) {
    // curr：探测指针，用于先检查当前剩余节点是否达到 k 个
    ListNode curr = head;
    // count：已探测节点数
    int count = 0;
    while (count < k) {
        // 不足 k 个时按题意保持原顺序，直接返回当前头
        if (curr == null) {
            return head;
        }
        curr = curr.next;
        count++;
    }

    // 节点数足够，开始反转当前这 k 个节点
    curr = head;
    // prev：已反转部分头节点，初始为空
    ListNode prev = null;
    for (int i = 0; i < k; i++) {
        // next：暂存后继，防止反转时断链
        ListNode next = curr.next;
        // 反转当前指针方向
        curr.next = prev;
        // prev/curr 同步前移
        prev = curr;
        curr = next;
    }

    // 反转后，原 head 变成这一组尾节点
    // 把它的 next 连接到“后续分组处理结果”
    head.next = reverseKGroup(curr, k);

    // prev 是当前这组反转后的新头节点
    return prev;
}

java

复杂度分析#

时间复杂度：O(n)，每个节点只处理一次
空间复杂度：O(n/k)，递归栈的深度

迭代解法：流水线作业#

如果说递归像是项目分配，那么迭代就像是流水线作业：我们站在生产线旁，一组一组地处理节点，每处理完一组就移动到下一组，直到处理完所有节点。

迭代实现#

public ListNode reverseKGroup(ListNode head, int k) {
    // dummy：虚拟头，便于处理第一组反转后的新头连接
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    // prevGroupTail：上一组反转后的尾节点（用于连接当前组新头）
    ListNode prevGroupTail = dummy;

    while (head != null) {
        // 1) 检查从 head 开始是否还有 k 个节点可反转
        ListNode tail = head;
        int count = 0;
        while (count < k && tail != null) {
            tail = tail.next;
            count++;
        }
        if (count < k) {
            // 不足 k 个，按题意保留原顺序并结束
            break;
        }

        // 2) 反转当前 k 个节点（区间：[head, tail)）
        ListNode curr = head;
        // prev 初始指向 tail，这样反转完成后当前组尾会自动接到下一组起点
        ListNode prev = tail;
        for (int i = 0; i < k; i++) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        // 3) 连接前后组
        // newGroupHead：当前组反转后的新头（即 prev）
        ListNode newGroupHead = prev;
        // oldGroupHead：当前组反转前的头，反转后会变成尾
        ListNode oldGroupHead = head;
        // 上一组尾巴接当前组新头
        prevGroupTail.next = newGroupHead;
        // 更新 prevGroupTail 为当前组新尾（oldGroupHead）
        prevGroupTail = oldGroupHead;
        // head 移动到下一组起点（tail）
        head = tail;
    }

    // 返回真实头节点
    return dummy.next;
}

java

图解过程#

以链表 1→2→3→4→5→6，k=3 为例：

1) 初始状态：
dummy → 1 → 2 → 3 → 4 → 5 → 6
  ↑
prevGroupTail

2) 第一组翻转后：
dummy → 3 → 2 → 1 → 4 → 5 → 6
              ↑
         prevGroupTail

3) 第二组翻转后：
dummy → 3 → 2 → 1 → 6 → 5 → 4
                          ↑
                     prevGroupTail

plaintext

两种解法的深度对比#

递归解法（项目分配型）：

优点：思路清晰，代码结构优雅
缺点：需要额外栈空间，不适合大规模数据
特点：自顶向下的处理方式，像层层分派任务

迭代解法（流水线型）：

优点：空间效率高，适合处理大规模数据
缺点：需要维护多个指针，逻辑较复杂
特点：自底向上的处理方式，像流水线作业

实现技巧总结#

使用虚拟头节点简化边界处理
先验证组内节点数量，再进行翻转
保存关键节点引用，便于后续连接
画图理清指针变化过程

难点剖析#

本题的主要难点在于：

如何准确判断剩余节点是否够一组
如何正确处理组间的连接
如何优雅地保持最后不足k个节点的原有顺序
如何在复杂的指针操作中避免断链

实际应用延伸#

这种分组处理的思想在实际开发中很常见：

批量数据处理
分布式计算任务划分
内存页面置换算法
消息队列的批量处理

小结#

K个一组翻转链表的问题教会我们：

如何将复杂问题分解为可管理的小问题
递归和迭代两种思维方式的优劣
在复杂的指针操作中保持逻辑清晰
如何通过实际场景理解抽象算法

这道题是链表操作的集大成者，它包含了：

链表翻转的基本技巧
分组处理的思想
递归与迭代的权衡
复杂场景下的边界处理

记住：解决复杂问题如同管理大型项目，关键在于合理的分解和清晰的思路！