双鸭山市网站建设_网站建设公司_前端工程师_seo优化

Java版LeetCode热题100之「K 个一组翻转链表」详解

本文约9200字，全面深入剖析 LeetCode 第25题《K 个一组翻转链表》。涵盖题目解析、模拟解法（含子链表反转）、复杂度分析、面试高频问答、实际开发应用场景、相关题目推荐等，助你彻底掌握链表分组操作的核心技巧。

一、原题回顾

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

• k是一个正整数，它的值小于或等于链表的长度。
• 如果节点总数不是k的整数倍，那么请将最后剩余的节点保持原有顺序。
• 你不能只是单纯地改变节点内部的值，而是需要实际进行节点交换。

示例 1：

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

示例 2：

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

提示：

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

进阶要求：
你可以设计一个只用O(1) 额外内存空间的算法解决此问题吗？

二、原题分析

这道题是「反转链表」的升级版，要求分组反转，且对不足k个的尾部保持原序。

核心挑战：

1. 分组判断：如何高效判断当前组是否满足k个节点？
2. 局部反转：如何只反转指定区间的子链表？
3. 连接上下文：反转后，如何将子链表重新接入原链表？
4. 头节点变更：第一组反转后，原head不再是头节点，如何正确返回？
5. 边界处理：空链表、k=1、k=n等特殊情况。

关键观察：

• 每次操作涉及四个关键节点：
  • pre：当前组的前驱（用于连接新头）
  • head：当前组的头
  • tail：当前组的尾
  • nextGroup：下一组的头（即tail.next）
• 反转后，原head变成尾，原tail变成头；
• 必须在反转前保存nextGroup，否则链表断裂；
• 使用虚拟头节点（hair）可统一处理头节点变更问题。

三、答案构思

总体策略：模拟 + 分段反转

1. 创建虚拟头节点hair，hair.next = head；
2. 初始化pre = hair，head = original head；
3. 循环处理每一组：
   • 从pre出发，走k步找到tail；
   • 若中途tail == null，说明不足k个，直接返回；
   • 保存nextGroup = tail.next；
   • 反转[head, tail]区间；
   • 将反转后的子链表接回：pre.next = newHead，newTail.next = nextGroup；
   • 更新pre = newTail，head = nextGroup；
4. 返回hair.next。

子问题：如何反转指定区间的链表？

参考「206. 反转链表」，但需注意：

• 反转终止条件不是null，而是tail；
• 初始prev应设为tail.next（即nextGroup），确保反转后尾部正确连接。

✅本题是“链表操作综合题”：融合了哑节点、指针移动、区间反转、连接修复等技巧。

四、完整答案（Java 实现）

/** * 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; } * } */classSolution{publicListNodereverseKGroup(ListNodehead,intk){// 创建虚拟头节点（"hair"），简化头节点处理ListNodehair=newListNode(0);hair.next=head;// pre 始终指向当前组的前驱节点ListNodepre=hair;// 循环处理每一组while(head!=null){// 1. 找到当前组的尾节点 tailListNodetail=pre;for(inti=0;i<k;i++){tail=tail.next;if(tail==null){// 不足 k 个，直接返回returnhair.next;}}// 2. 保存下一组的头节点ListNodenextGroup=tail.next;// 3. 反转 [head, tail] 区间// myReverse 返回 {newHead, newTail}ListNode[]reversed=myReverse(head,tail);ListNodenewHead=reversed[0];ListNodenewTail=reversed[1];// 4. 将反转后的子链表接回原链表pre.next=newHead;// 前驱连接新头newTail.next=nextGroup;// 新尾连接下一组// 5. 更新指针，准备处理下一组pre=newTail;head=nextGroup;}returnhair.next;}/** * 反转从 head 到 tail 的子链表（闭区间） * @return {newHead, newTail} 即 {tail, head} */privateListNode[]myReverse(ListNodehead,ListNodetail){// 关键：初始 prev 设为 tail.next，确保反转后尾部指向正确位置ListNodeprev=tail.next;ListNodecurrent=head;// 当 prev == tail 时，说明 head 到 tail 已全部反转while(prev!=tail){ListNodenextTemp=current.next;current.next=prev;prev=current;current=nextTemp;}// 返回 {新头, 新尾} = {原 tail, 原 head}returnnewListNode[]{tail,head};}}

✅该解法满足进阶要求：O(1) 额外空间！

五、代码分析

1. 虚拟头节点（hair）的作用

• 问题：第一组反转后，原head不再是头节点，如何返回正确结果？
• 解决方案：创建hair节点，hair.next = head。
• 效果：
  • 无论是否反转，最终头节点始终是hair.next；
  • pre初始为hair，天然成为第一组的“前驱”。

2. 分组与长度检查

ListNodetail=pre;for(inti=0;i<k;i++){tail=tail.next;if(tail==null)returnhair.next;}

• 从pre（前驱）出发，走k步到达tail；
• 若中途tail == null，说明剩余节点不足k个，直接返回。

3. 子链表反转逻辑（myReverse）

以[1,2,3]为例（k=3）：

• 初始：head=1,tail=3,prev = tail.next = 4
• 反转过程：
  • 1 → 4（断开原连接，指向下一组）
  • 2 → 1
  • 3 → 2
• 最终：3 → 2 → 1 → 4，返回{3, 1}

⚠️关键点：prev初始值必须是tail.next，否则反转后尾部会指向null，导致链表断裂！

4. 连接修复

pre.next=newHead;// 前一组的尾 → 新头newTail.next=nextGroup;// 新尾 → 下一组的头

• 完美衔接三部分：前缀 + 反转组 + 后缀

六、时间复杂度和空间复杂度分析

其中n为链表长度。

• 时间详解：
  • 外层循环执行⌊n/k⌋次；
  • 每次循环：找tail耗时 O(k)，反转耗时 O(k)；
  • 总时间 =⌊n/k⌋ × 2k ≈ 2n → O(n)
• 空间：无递归、无栈，纯迭代，满足进阶要求。

七、常见问题解答（FAQ）

Q1：为什么 myReverse 的终止条件是prev != tail？

答：
我们希望反转head到tail的所有节点。
初始prev = tail.next，每次循环prev前移一个节点。
当prev == tail时，说明tail也已完成反转（其next已指向原前驱），此时停止。
例如[1,2,3]：

• 初始：prev=4
• 第1轮：prev=1
• 第2轮：prev=2
• 第3轮：prev=3（== tail），停止

Q2：能否先遍历一次获取总长度，再分组？

答：可以，但不推荐。

• 优点：提前知道哪些组需要反转；
• 缺点：需要两次遍历，且代码更复杂；
  本题解法只需一次遍历，更优雅。

Q3：如果 k=1，会发生什么？

答：每个节点自成一组，反转后顺序不变。
代码仍正确运行：myReverse输入head=tail，直接返回{head, head}，连接不变。

Q4：为什么不用递归？

答：递归也可行，但：

• 空间复杂度 O(n/k)（递归栈）；
• 不符合“O(1) 空间”的进阶要求；
• 迭代解法更贴近工业实践。

八、优化思路

1. 提前计算总长度（可选）

// 先遍历一次获取 nintn=0;ListNodecur=head;while(cur!=null){n++;cur=cur.next;}// 然后只处理前 (n / k) * k 个节点

• 优点：避免在每组都检查长度；
• 缺点：多一次遍历，且n ≤ 5000时收益微乎其微。

2. 内联反转逻辑

将myReverse逻辑直接写入主函数，减少函数调用开销（JIT 通常会优化，意义不大）。

3. 工程化增强

• 输入校验：虽然题目保证1<=k<=n，但生产代码应检查k <= 0；
• 日志记录：调试时打印每组反转前后状态；
• 单元测试：覆盖k=1,k=n,n%k!=0等 case。

九、数据结构与算法基础知识点回顾

1. 链表反转（核心子问题）

• 单链表反转：维护prev,current,next
• 区间反转：需指定起止点，并正确连接外部

2. 虚拟头节点（Sentinel Node）

• 作用：消除头节点特殊处理
• 命名：常称dummy,hair,guard
• 适用场景：任何可能改变头节点的操作

3. 指针操作原则

• 先保存：在断开指针前，保存所有需要的引用
• 再连接：按依赖顺序更新指针
• 画图验证：复杂操作务必画图

4. 空间复杂度意识

• O(1) 空间：意味着不能使用递归、栈、额外数组
• 面试重点：进阶要求常考察空间优化能力

十、面试官提问环节（模拟）

❓ 问题1：你的解法中，myReverse 函数能否改为 void？

回答：
可以，但需要额外参数传递pre和nextGroup。
当前设计让myReverse职责单一（只负责反转），主函数负责连接，符合单一职责原则，代码更清晰。

❓ 问题2：如果要求从右往左每 k 个反转（如 [1,2,3,4,5], k=2 → [1,3,4,2,5]），怎么办？

回答：
这属于不同问题。可能需要：

1. 先计算总长度n；
2. 从位置n%k+1开始分组；
3. 或使用栈缓存前n%k个节点。
   但本题明确是“从左往右”分组。

❓ 问题3：你的算法能处理环形链表吗？

回答：
不能，且题目假设链表无环。
若存在环，找tail的循环会无限执行。
实际工程中，应先用 Floyd 判环算法检测，再处理。

❓ 问题4：为什么变量叫 hair 而不是 dummy？

回答：
这是 LeetCode 官方题解的命名习惯（“hair” as in “hare” from tortoise and hare algorithm）。
本质上和dummy一样，都是虚拟头节点。命名不影响逻辑，但建议使用更直观的dummyHead。

十一、这道算法题在实际开发中的应用

虽然“K 个一组反转”看似理论化，但其思想在实际系统中非常有用：

1.数据分块处理

• 大文件读取时，按固定块大小（k）处理；
• 反转可模拟“倒序处理块内数据”的需求。

2.网络协议中的分段重组

• TCP 分段传输后，接收端需按序重组；
• 若协议要求每 k 个包反向确认，可用类似逻辑。

3.音频/视频缓冲区管理

• 音频采样点存储在链表中；
• 某些特效（如回声）需分段反转播放。

4.任务批处理调度

• 任务队列按 k 个一批提交；
• 若需逆序执行批次内任务，可用此算法重排。

💡核心价值：训练分治思想和指针操作精度，这是系统编程的基石。

十二、相关题目推荐

掌握本题后，可挑战以下 LeetCode 题目：

建议按顺序练习，逐步构建链表操作知识体系。

十三、总结与延伸

✅ 本题核心收获

1. 分组处理思想：将大问题分解为重复子问题（每组反转）；
2. 虚拟头节点：优雅解决头节点变更和边界问题；
3. 区间反转技巧：通过设置正确的prev初始值，实现精准反转；
4. O(1) 空间意识：迭代优于递归，符合工业级要求。

🔮 延伸思考

• 双向链表如何实现？
  需额外维护prev指针，反转时同步更新，逻辑更复杂。

• 能否并行处理各组？
  理论上可以（各组独立），但链表非随机访问，实际难以并行化。

• 函数式解法？
  在支持不可变数据结构的语言中，需重建节点，空间开销大。

🌟 最后建议

• 手写代码：在白板上写出主循环和反转逻辑，确保无 bug；
• 讲清思路：面试时先说“我打算用虚拟头节点+分段反转”，再解释细节；
• 主动测试：提出测试k=1,k=n,n=5,k=3等 case，展现全面性。

“链表题，分而治之是策略，指针操作是基本功。”
掌握本题，你就拥有了处理复杂链表变形的利器。继续前行，算法之路越走越宽！