知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 05 - K个一组翻转链表 ## 题目(LeetCode 25) 给你链表的头节点 head,每 k 个节点一组进行翻转,返回修改后的链表。不足 k 个的保持原样。 ## 大白话理解 先数够 k 个,翻转这一段,然后递归处理剩下的。 ## 解法 ```java class Solution { public ListNode reverseKGroup(ListNode head, int k) { // 先检查是否够 k 个 ListNode node = head; for (int i = 0; i < k; i++) { if (node == null) return head; // 不够 k 个,直接返回 node = node.next; } // 翻转前 k 个 ListNode prev = null, curr = head; for (int i = 0; i < k; i++) { ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; } // head 变成了这一组的尾部,接上后面递归的结果 head.next = reverseKGroup(curr, k); return prev; } } ``` ## 复杂度 - 时间 O(n),空间 O(n/k) 递归栈 > 💬 **Q:还有其他解法吗?** > > 有迭代解法,用 dummy 节点 + 四个指针,空间降到 O(1)。 > > 四个指针的含义: > - `prevGroupTail`:上一组的尾节点(用来连接当前组翻转后的头) > - `groupHead`:当前组的头节点(翻转后变成尾) > - `groupTail`:当前组的尾节点(翻转后变成头) > - `nextGroupHead`:下一组的头节点(翻转后 groupHead.next 要指向它) > > ```java > class Solution { > public ListNode reverseKGroup(ListNode head, int k) { > ListNode dummy = new ListNode(0, head); > ListNode prevGroupTail = dummy; > > while (true) { > // 1. 找到当前组的尾节点(走 k 步) > ListNode groupTail = prevGroupTail; > for (int i = 0; i < k; i++) { > groupTail = groupTail.next; > if (groupTail == null) return dummy.next; // 不够 k 个,结束 > } > > ListNode groupHead = prevGroupTail.next; > ListNode nextGroupHead = groupTail.next; > > // 2. 翻转 [groupHead, groupTail] 这一段 > ListNode prev = nextGroupHead, curr = groupHead; > while (curr != nextGroupHead) { > ListNode next = curr.next; > curr.next = prev; > prev = curr; > curr = next; > } > // 翻转后:groupTail 变成了这组的新头,groupHead 变成了新尾 > > // 3. 连接:上一组尾 → 当前组新头(groupTail) > prevGroupTail.next = groupTail; > // groupHead(现在是尾)已经指向 nextGroupHead(在翻转时设置了) > > // 4. 移动 prevGroupTail 到当前组的尾部,准备处理下一组 > prevGroupTail = groupHead; > } > } > } > ``` > > 两种解法对比: > > | | 递归 | 迭代 | > |--|------|------| > | 空间复杂度 | O(n/k)(调用栈) | O(1) | > | 代码简洁度 | 更简洁 | 稍复杂 | > | 面试推荐 | 先写递归,再说能优化到 O(1) | 追问时给出 | ## 一句话总结 先检查够不够 k 个,够就翻转这一段,然后递归处理剩余部分。 --- 下一篇:[06 - 三数之和](./06-three-sum.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入