K 个一组翻转链表

1. 问题描述

1.1 题目定义

LeetCode 25. 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]

输入：head = [1,2,3,4,5,6,7,8], k = 3
输出：[3,2,1,6,5,4,7,8]

1.2 约束条件

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

1.3 链表节点定义

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; }
}

2. 问题分析

2.1 核心难点

1. 分组检测：需要先检查剩余节点是否足够k个
2. 局部反转：对每k个节点进行反转操作
3. 连接管理：反转后需要正确连接各组之间的关系
4. 边界处理：最后不足k个节点的组保持原序

2.2 解题思路

• 递归方法：先处理前k个节点，再递归处理剩余部分
• 迭代方法：使用指针逐组处理，维护连接关系

3. 递归解法

3.1 算法思路

1. 检查从当前节点开始是否有k个节点
2. 如果不足k个，直接返回head（保持原序）
3. 如果足够k个，反转这k个节点
4. 递归处理剩余部分并连接

3.2 代码实现

public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k == 1) return head;
        
        // 检查是否有k个节点
        ListNode curr = head;
        for (int i = 0; i < k; i++) {
            if (curr == null) {
                return head;  // 不足k个节点，保持原序
            }
            curr = curr.next;
        }
        
        // 反转前k个节点
        ListNode newHead = reverse(head, curr);
        
        // 递归处理剩余部分
        head.next = reverseKGroup(curr, k);
        
        return newHead;
    }
    
    /**
     * 反转[start, end)区间的节点
     * @param start 起始节点（包含）
     * @param end 结束节点（不包含）
     * @return 反转后的新头节点
     */
    private ListNode reverse(ListNode start, ListNode end) {
        ListNode prev = null;
        ListNode curr = start;
        
        while (curr != end) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }
}

3.3 递归过程图解

原链表：1 -> 2 -> 3 -> 4 -> 5 -> 6, k = 3

第一次递归：
- 检查节点1,2,3（足够3个）
- 反转1,2,3 得到：3 -> 2 -> 1
- 递归处理4,5,6

第二次递归：
- 检查节点4,5,6（足够3个）
- 反转4,5,6 得到：6 -> 5 -> 4
- 递归处理null（结束）

连接结果：3 -> 2 -> 1 -> 6 -> 5 -> 4

4. 迭代解法

4.1 算法思路

1. 使用虚拟头节点简化边界处理
2. 维护prev指针指向当前组的前一个节点
3. 找到当前组的起始和结束节点
4. 反转当前组并更新连接关系
5. 移动到下一组继续处理

4.2 代码实现

public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k == 1) return head;
        
        // 创建虚拟头节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        ListNode prev = dummy;  // 当前组的前一个节点
        
        while (true) {
            // 检查剩余节点是否足够k个
            ListNode end = prev;
            for (int i = 0; i < k; i++) {
                end = end.next;
                if (end == null) {
                    return dummy.next;  // 不足k个，结束处理
                }
            }
            
            ListNode start = prev.next;  // 当前组的第一个节点
            ListNode nextGroup = end.next;  // 下一组的第一个节点
            
            // 断开当前组与后续节点的连接
            end.next = null;
            
            // 反转当前组
            prev.next = reverseList(start);
            
            // 连接到下一组
            start.next = nextGroup;
            
            // 移动prev到下一组的前一个节点
            prev = start;
        }
    }
    
    /**
     * 反转链表（标准反转）
     */
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }
}

4.3 迭代过程图解

原链表：1 -> 2 -> 3 -> 4 -> 5, k = 3

初始状态：
dummy -> 1 -> 2 -> 3 -> 4 -> 5
prev

第一轮：
- start = 1, end = 3, nextGroup = 4
- 反转1->2->3 得到 3->2->1
- 连接：dummy -> 3 -> 2 -> 1 -> 4 -> 5
                              prev

第二轮：
- 检查剩余节点4,5（不足3个）
- 结束处理

最终结果：3 -> 2 -> 1 -> 4 -> 5

5. 优化版本

5.1 一次遍历优化

public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k == 1) return head;
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        
        while (prev.next != null) {
            // 检查并找到当前组的结束位置
            ListNode end = prev;
            for (int i = 0; i < k && end != null; i++) {
                end = end.next;
            }
            
            if (end == null) break;  // 不足k个节点
            
            ListNode start = prev.next;
            ListNode nextGroup = end.next;
            
            // 原地反转当前组
            reverseRange(prev, start, end, nextGroup);
            
            // 更新prev指针
            prev = start;
        }
        
        return dummy.next;
    }
    
    /**
     * 原地反转[start, end]范围的节点
     */
    private void reverseRange(ListNode prev, ListNode start, ListNode end, ListNode nextGroup) {
        ListNode curr = start;
        ListNode next = start.next;
        
        // 反转内部连接
        while (next != nextGroup) {
            ListNode temp = next.next;
            next.next = curr;
            curr = next;
            next = temp;
        }
        
        // 更新外部连接
        prev.next = end;
        start.next = nextGroup;
    }
}

6. 复杂度分析

方法	时间复杂度	空间复杂度	特点
递归解法	O(n)	O(n/k)	代码简洁，有递归栈开销
迭代解法	O(n)	O(1)	空间效率高，逻辑稍复杂
优化版本	O(n)	O(1)	原地操作，最优解

时间复杂度分析：

• 每个节点最多被访问常数次（检查、反转、连接）
• 总体时间复杂度为O(n)

空间复杂度分析：

• 递归版本：递归深度为n/k，空间复杂度O(n/k)
• 迭代版本：只使用常数个指针变量，空间复杂度O(1)

7. 边界情况处理

7.1 测试用例

public class TestReverseKGroup {
    public static void main(String[] args) {
        Solution solution = new Solution();
        
        // 测试用例1：空链表
        ListNode result1 = solution.reverseKGroup(null, 3);
        System.out.println("空链表：" + (result1 == null ? "null" : "非null"));
        
        // 测试用例2：k=1（不需要反转）
        ListNode head2 = createList(new int[]{1, 2, 3, 4, 5});
        ListNode result2 = solution.reverseKGroup(head2, 1);
        printList(result2);  // 输出：1 -> 2 -> 3 -> 4 -> 5
        
        // 测试用例3：链表长度小于k
        ListNode head3 = createList(new int[]{1, 2});
        ListNode result3 = solution.reverseKGroup(head3, 3);
        printList(result3);  // 输出：1 -> 2
        
        // 测试用例4：链表长度等于k
        ListNode head4 = createList(new int[]{1, 2, 3});
        ListNode result4 = solution.reverseKGroup(head4, 3);
        printList(result4);  // 输出：3 -> 2 -> 1
        
        // 测试用例5：链表长度是k的倍数
        ListNode head5 = createList(new int[]{1, 2, 3, 4, 5, 6});
        ListNode result5 = solution.reverseKGroup(head5, 3);
        printList(result5);  // 输出：3 -> 2 -> 1 -> 6 -> 5 -> 4
        
        // 测试用例6：链表长度不是k的倍数
        ListNode head6 = createList(new int[]{1, 2, 3, 4, 5});
        ListNode result6 = solution.reverseKGroup(head6, 3);
        printList(result6);  // 输出：3 -> 2 -> 1 -> 4 -> 5
    }
    
    // 辅助方法：创建链表
    public static ListNode createList(int[] vals) {
        if (vals.length == 0) return null;
        
        ListNode head = new ListNode(vals[0]);
        ListNode curr = head;
        
        for (int i = 1; i < vals.length; i++) {
            curr.next = new ListNode(vals[i]);
            curr = curr.next;
        }
        
        return head;
    }
    
    // 辅助方法：打印链表
    public static void printList(ListNode head) {
        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val);
            if (curr.next != null) System.out.print(" -> ");
            curr = curr.next;
        }
        System.out.println();
    }
}

7.2 边界条件总结

1. 空链表：直接返回null
2. k=1：相当于不反转，直接返回原链表
3. 链表长度 < k：保持原序，不进行反转
4. 链表长度 = k：整个链表反转
5. 链表长度 > k但不是k的倍数：最后剩余部分保持原序

8. 相关变种问题

8.1 两两交换链表中的节点

LeetCode 24： K个一组翻转链表当k=2时的特殊情况

public class Solution {
    public ListNode swapPairs(ListNode head) {
        return reverseKGroup(head, 2);
    }
    
    // 或者专门优化的版本
    public ListNode swapPairsOptimized(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        
        while (prev.next != null && prev.next.next != null) {
            ListNode first = prev.next;
            ListNode second = prev.next.next;
            
            // 交换两个节点
            prev.next = second;
            first.next = second.next;
            second.next = first;
            
            // 移动prev指针
            prev = first;
        }
        
        return dummy.next;
    }
}

8.2 反转链表指定区间

LeetCode 92： 反转从位置m到n的链表

public class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == right) return head;
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        
        // 移动到left的前一个位置
        for (int i = 1; i < left; i++) {
            prev = prev.next;
        }
        
        ListNode start = prev.next;
        ListNode end = start;
        
        // 找到right位置的节点
        for (int i = left; i < right; i++) {
            end = end.next;
        }
        
        ListNode nextGroup = end.next;
        end.next = null;
        
        // 反转[left, right]区间
        prev.next = reverseList(start);
        start.next = nextGroup;
        
        return dummy.next;
    }
    
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }
}

8.3 旋转链表

LeetCode 61： 给定链表，旋转链表，使得每个节点向右移动k个位置

public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }
        
        // 计算链表长度并形成环
        ListNode tail = head;
        int length = 1;
        while (tail.next != null) {
            tail = tail.next;
            length++;
        }
        tail.next = head;  // 形成环
        
        // 计算实际旋转步数
        k = k % length;
        int stepsToNewTail = length - k;
        
        // 找到新的尾节点
        ListNode newTail = head;
        for (int i = 1; i < stepsToNewTail; i++) {
            newTail = newTail.next;
        }
        
        ListNode newHead = newTail.next;
        newTail.next = null;  // 断开环
        
        return newHead;
    }
}

9. 性能优化技巧

9.1 减少重复遍历

public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k == 1) return head;
        
        // 一次遍历计算总长度
        int length = getLength(head);
        if (length < k) return head;
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        
        // 只处理完整的k组
        int groups = length / k;
        for (int i = 0; i < groups; i++) {
            prev = reverseNextKNodes(prev, k);
        }
        
        return dummy.next;
    }
    
    private int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }
    
    private ListNode reverseNextKNodes(ListNode prev, int k) {
        ListNode start = prev.next;
        ListNode curr = start;
        
        // 找到第k个节点
        for (int i = 1; i < k; i++) {
            curr = curr.next;
        }
        
        ListNode nextGroup = curr.next;
        curr.next = null;
        
        // 反转k个节点
        prev.next = reverseList(start);
        start.next = nextGroup;
        
        return start;  // 返回新的prev位置
    }
    
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }
}

9.2 原地反转优化

public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k == 1) return head;
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        
        while (hasKNodes(prev.next, k)) {
            prev = reverseKNodesInPlace(prev, k);
        }
        
        return dummy.next;
    }
    
    private boolean hasKNodes(ListNode head, int k) {
        for (int i = 0; i < k && head != null; i++) {
            head = head.next;
        }
        return head != null || k == 0;
    }
    
    private ListNode reverseKNodesInPlace(ListNode prev, int k) {
        ListNode start = prev.next;
        ListNode curr = start.next;
        
        // 使用头插法原地反转
        for (int i = 1; i < k; i++) {
            start.next = curr.next;
            curr.next = prev.next;
            prev.next = curr;
            curr = start.next;
        }
        
        return start;
    }
}

10. 实际应用场景

10.1 数据处理

• 批量数据重组：将数据按固定大小分组并重新排列
• 内存块管理：操作系统中的内存块重组
• 网络数据包处理：按协议要求重组数据包

10.2 算法设计

• 分治算法：将大问题分解为固定大小的子问题
• 并行处理：将任务分组后并行执行
• 缓存优化：按缓存行大小重组数据提高访问效率

10.3 系统设计

• 负载均衡：将请求按组分发到不同服务器
• 数据库分片：按固定规则重组数据分布
• 消息队列：批量处理消息以提高吞吐量

11. 常见错误与调试

11.1 常见错误

1. 指针更新顺序错误：导致链表断裂或形成环
2. 边界条件遗漏：未处理k=1或链表长度小于k的情况
3. 连接关系错误：反转后未正确连接各组
4. 内存泄漏：在某些语言中未正确管理节点内存

11.2 调试技巧

public class DebugHelper {
    // 可视化链表分组
    public static void printGroups(ListNode head, int k) {
        ListNode curr = head;
        int count = 0;
        
        System.out.print("Groups: ");
        while (curr != null) {
            if (count % k == 0 && count > 0) {
                System.out.print(" | ");
            }
            System.out.print(curr.val + " ");
            curr = curr.next;
            count++;
        }
        System.out.println();
    }
    
    // 检查链表完整性
    public static boolean validateList(ListNode head, int expectedLength) {
        Set<ListNode> visited = new HashSet<>();
        ListNode curr = head;
        int actualLength = 0;
        
        while (curr != null) {
            if (visited.contains(curr)) {
                System.out.println("检测到环形链表！");
                return false;
            }
            visited.add(curr);
            actualLength++;
            curr = curr.next;
        }
        
        if (actualLength != expectedLength) {
            System.out.println("链表长度不匹配：期望" + expectedLength + "，实际" + actualLength);
            return false;
        }
        
        return true;
    }
    
    // 步骤跟踪
    public static void traceStep(String step, ListNode head) {
        System.out.print(step + ": ");
        printList(head);
    }
    
    private static void printList(ListNode head) {
        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val);
            if (curr.next != null) System.out.print(" -> ");
            curr = curr.next;
        }
        System.out.println();
    }
}

12. 总结

12.1 核心要点

1. 分组思想：将链表按k个节点分组处理
2. 局部反转：每组内部进行标准链表反转
3. 连接管理：维护组与组之间的正确连接
4. 边界处理：最后不足k个节点的组保持原序

12.2 算法选择建议

• 递归解法：代码简洁，适合理解算法思想
• 迭代解法：空间效率高，适合生产环境
• 优化版本：性能最佳，适合对性能要求严格的场景

12.3 学习建议

1. 掌握基础反转：先熟练掌握基本链表反转
2. 理解分组逻辑：重点理解如何检测和处理k个节点的分组
3. 练习指针操作：通过画图理解指针的更新顺序
4. 注重边界条件：仔细处理各种边界情况

12.4 进阶方向

• 双向链表的k组反转
• 循环链表的k组反转
• 多线程环境下的链表操作
• 基于k组反转的其他算法应用

K个一组翻转链表是链表操作中的经典难题，它综合考查了链表反转、指针操作、分组处理等多个知识点。通过深入理解这个问题，可以为解决更复杂的链表算法打下坚实基础。