从项目分配到链表翻转：探索K组翻转的管理艺术｜LeetCode 25 K个一组翻转链表

生活中的分组管理

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

问题描述

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

例如：

输入：1 → 2 → 3 → 4 → 5，k = 2
输出：2 → 1 → 4 → 3 → 5

输入：1 → 2 → 3 → 4 → 5，k = 3
输出：3 → 2 → 1 → 4 → 5

输入：1 → 2 → 3 → 4 → 5，k = 1
输出：1 → 2 → 3 → 4 → 5

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

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

递归思路解析

就像项目分配一样：

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

递归实现

public ListNode reverseKGroup(ListNode head, int k) {
    // 先看看手上有没有k个节点
    ListNode curr = head;
    int count = 0;
    while (count < k) {
        if (curr == null) {
            return head; // 不够k个，保持原样
        }
        curr = curr.next;
        count++;
    }
    
    // 够k个，开始处理当前这一组
    curr = head;
    ListNode prev = null;
    for (int i = 0; i < k; i++) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    
    // 让"下属"处理后续节点，并把结果接在当前组后面
    head.next = reverseKGroup(curr, k);
    
    return prev; // 返回当前组的新头节点
}

复杂度分析

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

迭代解法：流水线作业

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

迭代实现

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode prevGroupTail = dummy;
    
    while (head != null) {
        // 1. 检查是否还有k个节点
        ListNode tail = head;
        int count = 0;
        while (count < k && tail != null) {
            tail = tail.next;
            count++;
        }
        if (count < k) {
            break; // 不够k个，结束处理
        }
        
        // 2. 翻转当前k个节点
        ListNode curr = head;
        ListNode prev = tail; // 注意：连接到下一组的头部
        for (int i = 0; i < k; i++) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        // 3. 连接前后
        ListNode newGroupHead = prev;  // 当前组翻转后的头节点
        ListNode oldGroupHead = head;  // 记住原来的头节点，它将成为新的尾节点
        prevGroupTail.next = newGroupHead;
        prevGroupTail = oldGroupHead;
        head = tail;  // 移动到下一组的开始
    }
    
    return dummy.next;
}

图解过程

以链表 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

两种解法的深度对比

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

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

迭代解法（流水线型）：

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

实现技巧总结

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

难点剖析

本题的主要难点在于：

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

实际应用延伸

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

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

小结

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

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

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

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

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

---

作者：忍者算法 公众号：忍者算法

我准备了一份刷题清单，以及这些题目的详细题解，覆盖了绝大部分常见面试题。我可以很负责任地说，只要你把这些题真正掌握了，80%的算法面试都能遇到相似题目。公众号回复【刷题清单】获取～