数据结构算法系列写到链表篇的时候我一直在琢磨怎么把反转这个话题讲透。很多人习惯性地把题目分成数组题、字符串题、链表题好像数据结构不同解法就必须完全不同。但刷到一定量之后你会发现真正决定解法的往往是问题结构而不是数据结构的形态。反转字符串II就是很典型的一道题它表面上是字符串题可它的核心套路和链表里的每k个一组反转链表几乎是同一个思路——按固定长度分组再对组内区间做反转。所以我特意把这道题放进链表篇做对照用一道题把字符串反转和链表反转两条线串到一起顺便把边界条件一次讲清楚。如果你是刚开始刷算法题或者正在准备面试这篇文章应该能帮你省不少时间。我会从题目规则拆解开始讲到完整可跑的代码再延伸到链表反转的实现最后把我在实际调试中踩过的坑列出来。跟着走一遍你收获的不只是这一道题的解法而是一类分组反转问题的通用框架。1. 反转字符串II是一道披着字符串外衣的分组反转题1.1 题目规则拆解不是反转整个字符串而是每隔 2k 反转前 k 个这道题在算法题库里的编号是541题目描述很简短但信息量不小给定一个字符串 s 和一个整数 k从字符串开头算起每计数至 2k 个字符就反转这 2k 个字符中的前 k 个字符。后面还有两条补充规则如果剩余字符少于 k 个则将剩余字符全部反转如果剩余字符小于 2k 但大于或等于 k 个则反转前 k 个字符其余字符保持原样。第一次看的反应往往是这不就是一个双指针交换吗但真动手写的时候你会发现每 2k 个字符这个分组条件才是关键。拿官网的经典示例拆一遍s abcdefgk 2。先看下标 0 到 3也就是 abcd这是完整的一组 2k 个字符。按照规则只反转前 k 个字符也就是反转 ab得到 ba所以第一组处理完变成 bacd。再看剩下的 efg总共 3 个字符。3 大于等于 k2但小于 2k4于是归入第二条规则只反转前 k 个字符也就是反转 ef得到 fe最后一个字符 g 保持不动。最终结果是 bacdfeg。再看一个 k3 的例子s abcdefghij。前 6 个字符 abcdef 是一组反转前 3 个变成 cbadef。剩下 ghij 一共 4 个字符4 大于等于 3 但小于 6所以反转前 3 个 ghi得到 ihg最后的 j 不动。最终结果是 cbadefhgji。这两个例子走完你应该能感觉到题目本身没有高深技巧真正的难点全在分组的边界和最后一组怎么处理上。而这恰恰是很多人写错的地方后面我会专门讲。1.2 为什么这道字符串题会出现在链表篇系列里我写这个系列时一直在强调一个观点数组、字符串支持随机访问定位区间只需要两个下标链表只能靠指针一步一步走定位区间要麻烦得多。但抛开访问方式的差异这两类题的内核完全一致——都是对一个线性序列按固定步长切块再对切出来的区间做反转操作。这个系列的链表篇前面已经讲过反转整个链表、反转链表的前 N 个节点指针操作的细节大家应该比较熟了。这时候放一道字符串题进来不是为了凑数而是想让大家看到同一个框架在不同数据结构上是怎么落地的。反转字符串II节奏是步长为 2k 分组反转组内前 k 个而链表题每 k 个一组反转链表节奏是按 k 个节点分组反转组内全部节点。两者都包含两层循环思维外层管分组移动内层管区间反转。很多面试题看起来吓人其实就是把这种熟悉的套路换了一个数据结构包装。你提前把这种分组反转的通用解法想明白面试时遇到变体题就从容得多。2. 核心思路先分组再反转组内区间2.1 i 2k 而不是 i k这是最容易写错的一行这个解法最核心的一行代码就是循环步长。我见过很多人第一次写这道题都写成i k理由是每组要反转前 k 个那处理完一组就前进 k 个位置。这个理由听起来合理其实是错的。建议你仔细想一下分组结构每一轮处理的是一个长度为 2k 的窗口窗口里前半段要反转后半段是原样保留的。所以处理完当前窗口之后下一轮的起点必须跳过整个窗口也就是向后移动 2k 个位置。如果只移动 k 个位置下一轮就会从上一轮保留的那 k 个字符开始把不该反转的内容又反转了一遍。举个例子s abcdefghijk 2。下标 0 到 3 是一组第一轮反转 ab 得到 bacd。如果下一步i 4下一轮从下标 4 开始处理 efgh这是正确的。但如果错误地写成i 2下一轮就从下标 2 开始把上一轮保留的 c、d 当成新一组的前半段去反转结果整个字符串会被搅得乱七八糟。所以最稳妥的写法就是for (int i 0; i n; i 2 * k) { // 处理以 i 开头的一组 }这一行想通整道题的框架就稳了。2.2 反转区间边界统一用 min(i k, n) 处理分组步长确定之后下一步是确定当前这一轮要反转的区间到底是从哪到哪。规则很清晰反转区间长度是 k起点是 i终点理论上是 i k - 1。但最后一组可能不足 k 个字符这时终点就变成了 n - 1。两个规则合并起来终点可以写成int right Math.min(i k - 1, n - 1);这里Math.min的作用是防止越界。当i k - 1大于等于n - 1时说明剩余字符不足 k 个终点自动收窄到 n - 1也就是把剩余字符全部反转。当i k - 1小于n - 1时说明这一组至少有 k 个字符正常反转前 k 个即可。如果你喜欢用开区间思维也可以写成这样int end Math.min(i k, n); // end 是反转区间的开区间右边界两种写法本质一样但开区间版本在配合substring或切片操作时更容易配对不容易出现差一错误。我个人的习惯是用开区间因为后面判断本组后半段从哪到哪时会更清晰。2.3 两种代码实现对比双指针版与 StringBuilder 版先看最朴素的双指针版本用 Java 实现。思想是把字符串转成字符数组然后对每个分组区间做头尾交换public String reverseStr(String s, int k) { char[] arr s.toCharArray(); int n arr.length; for (int i 0; i n; i 2 * k) { int left i; int right Math.min(i k - 1, n - 1); while (left right) { char tmp arr[left]; arr[left] arr[right]; arr[right] tmp; left; right--; } } return new String(arr); }这个版本最贴近题目本质每一步都在做定位区间 双指针交换。代码量少也不容易被 StringBuilder 的切片逻辑绕晕。我建议面试时优先写这个版本思路一眼就能讲清楚。再看一个用 StringBuilder 的版本。它的思路是逐个处理分组前 k 个字符反转后追加后 k 个字符如果有原样追加public String reverseStr(String s, int k) { StringBuilder sb new StringBuilder(); int n s.length(); for (int i 0; i n; i 2 * k) { int mid Math.min(i k, n); // 本组要反转部分的结束位置开区间 StringBuilder sub new StringBuilder(s.substring(i, mid)); sb.append(sub.reverse()); // 反转前 k 个 int restEnd Math.min(i 2 * k, n); // 本组后半段的结束位置开区间 if (restEnd mid) { sb.append(s.substring(mid, restEnd)); // 后半段原样保留 } } return sb.toString(); }这个版本在理解开区间时会稍微费一点脑子但好处是代码结构非常贴合题目描述先反转前 k 个再保留剩下的。两种实现我都跑过结果一致。个人建议是如果面试官让你实现优先写字符数组版如果是日常刷题可以用 StringBuilder 版加深对区间的理解。2.4 复杂度分析与极值测试时间复杂度是 O(n)因为每个字符最多被访问两次一次是确认为当前窗口的前半段或后半段另一次是在反转时被交换。无论哪种实现都没有嵌套的多重循环所以线性复杂度是确定的。空间复杂度需要注意语言差异。Java 的 String 是不可变的转成char[]本身就是 O(n) 的额外空间。StringBuilder 版本里substring会创建新的字符串累计空间也是 O(n)。如果是在 C 里直接对string原地操作或者 Go 里对[]byte原地操作额外空间可以是 O(1)。这一点在面试时主动说出来能体现你对语言特性的了解。提交代码之前建议先用几个极值测试自测k 1 时反转前 1 个字符等于不反转结果应该和原字符串一致k 大于等于字符串长度时整个字符串应该被反转空字符串应该直接返回空串。这几个用例能帮你把大多数边界错误挡在提交之前。3. 把字符串反转的思路迁移到链表上3.1 为什么链表不能像字符串那样用双下标字符串反转的核心是任意位置都能 O(1) 访问所以两个下标一前一后往中间靠拢交换元素就行。链表不行你要访问第 j 个节点只能从头部开始逐个 next定位成本是 O(j)。想在链表上反转一个区间不能靠下标交换只能靠改变节点之间的指向。打个比方一排人面朝右站现在要让他们全部面朝左。数组的做法是让最左边的人和最右边的人互换位置效率很高链表却是每个人只有一条手搭在前面一个人肩膀上你要让整排人转身只能从一端开始一个一个把手的朝向调过来。这就是为什么链表的反转代码里全是prev、curr、next这三个指针。理解了这个差异你再看链表反转代码就不会觉得是在背模板了——它只是在顺着链表的结构特性做事。3.2 反转整个链表三指针迭代法与递归法先看最基础的迭代反转。假设链表是 1 - 2 - 3 - 4 - null目标是变成 4 - 3 - 2 - 1 - null。public ListNode reverseList(ListNode head) { ListNode prev null; ListNode curr head; while (curr ! null) { ListNode next curr.next; // 先保存下一个节点否则改动 curr.next 后会丢失 curr.next prev; // 掉转当前节点的指针方向 prev curr; // prev 前进 curr next; // curr 前进 } return prev; }每一步走一遍你就明白了初始 prev 是 nullcurr 是节点 1。第一轮先把 next 存成节点 2然后让 1.next null此时节点 1 变成了尾节点接着 prev 节点 1curr 节点 2。第二轮让 2.next 节点 1prev 变成节点 2curr 变成节点 3。这样一轮一轮下去原头节点 1 的 next 最终指向 null新的头节点 4 被返回。这里有一个细节值得注意第一次迭代就把head.next设成了 null。这正是反转后的尾节点该有的样子如果不做这一步链表里会出现环。递归版本也很经典思路是假设当前节点的后面已经被反转好了我只需要把自己接到这段反转链表的末尾public ListNode reverseList(ListNode head) { if (head null || head.next null) { return head; } ListNode newHead reverseList(head.next); head.next.next head; // head.next 此时是反转后的尾节点 head.next null; // 当前节点变成新的尾节点 return newHead; }递归版代码更短但对新手来说有点绕。我建议先把迭代版写熟练再回过头来看递归版两个都掌握之后遇到反转区间链表这种进阶题会轻松很多。3.3 每 k 个一组反转链表分组反转思想的链表落地现在回到正题如果把这个分组反转思想放到链表上就是题库里另一道名题每 k 个一组反转链表。先看一下这道题的要求给定一个链表每 k 个节点一组进行反转最后一组如果不足 k 个节点则保持原样。这和字符串版的规则几乎一一对应只不过字符串版是每 2k 个字符一组反转前 k 个而链表版是每 k 个节点一组反转整组。实现需要几个辅助指针。我用一个 dummy 节点来避免对头节点做额外判断然后不断重复走 k 步检查够不够 - 反转当前组 - 接回原链表这个过程public ListNode reverseKGroup(ListNode head, int k) { ListNode dummy new ListNode(0); dummy.next head; ListNode pre dummy; // pre 始终指向上一组的尾节点 ListNode tail dummy; // tail 用来探路判断当前组是否够 k 个 while (tail.next ! null) { // 1. tail 先走 k 步如果走到 null 说明剩余不足 k 个 for (int i 0; i k tail ! null; i) { tail tail.next; } if (tail null) { break; // 剩余节点不足一组保持原样返回 } ListNode start pre.next; // 当前组的第一个节点 ListNode nextGroup tail.next; // 下一组的第一个节点 // 2. 把当前组从原链表中切出来单独反转 tail.next null; pre.next reverseList(start); // 3. 反转后 start 变成了当前组的尾节点把它接回下一组 start.next nextGroup; // 4. 移动 pre 到当前组的尾节点准备下一轮 pre start; tail pre; } return dummy.next; }这里的reverseList就是前面写的迭代反转函数。因为我们在反转前已经用tail.next null把当前组切成了独立链表所以reverseList(start)只会反转这一组内部的指针关系。把这道链表题和字符串题放在一张表里对照很多抽象的东西一下就清晰了维度反转字符串II每k个一组反转链表分组步长每 2k 个字符一组反转前 k 个每 k 个节点一组反转整组区间定位下标 i k用 min 防止越界tail 指针先走 k 步探路反转手段双指针头尾交换字符prev/curr/next 三指针改指向连接方式后半段原样保留天然拼接需要把组尾手动接到下一组开头最后一组不足 k 个全部反转不足 k 个保持原样我写代码的时候经常把这张表默背一遍确认自己当前写的是哪个版本。一旦混了比如在字符串题里把不足 k 个当成保持原样一提交就会有反例直接教你做人。4. 实战中的高频错误与避坑建议4.1 循环步长写错全盘错乱的典型样例前面反复强调的i 2k我还是要单独拿出来说一次因为这个错的隐蔽性确实高。我见过不少基础不错的同学思路完全正确代码写到循环那行手一滑就写成i k然后对着错误用例看半天怎么也想不通。给你一个直观的错误样例。s abcdefghijk 2正确结果是 bacdfe hgij 格式当然是 bacdfehgij。如果步长错误地写成加上 k也就是 2过程会是这样i0 反转 abi2 时因为上一轮保留了 cd现在又从 c 开始反转 cd得到 dci4 反转 ef等等。最后你会发现偶数位的字符几乎都被翻转了一次整个字符串面目全非。所以提交前先花十秒钟心算一个小例子确认循环变量的跳法是 2k。这个习惯成本极低收益极高。这里我不妨说得再直接一点我自己的经验是这道题只要循环步长写对边界用 min 包一下基本就没有什么压轴坑了。4.2 最后一组的两条规则不能混为一谈很多人在剩余字符不足 2k 但不少于 k和剩余字符少于 k这两种场景之间犯迷糊。前者要只反转前 k 个后者要全部反转。如果你用right Math.min(i k - 1, n - 1)这个公式两个场景会被自动区分如果剩余字符大于等于 k那么i k - 1一定小于n - 1min 会取前者正好只是反转前 k 个。如果剩余字符少于 k那么i k - 1会超过n - 1min 会取后者相当于把剩下的字符全部反转。一句话不要写两个 if 去分支统一用一个 min 就能覆盖全部情况。这是我处理区间问题时最常用的技巧遇到不确定边界的时候优先想怎么用一个上界约束写出来而不是不停加条件分支。4.3 语言特性带来的原地反转陷阱还有一个细节容易被忽略不同的语言里字符串的可变性差别很大这会直接影响你写法的选择。Java 的 String 不可变你必须先转char[]或者用StringBuilder才能修改。Python 的字符串也不可变很多新手图省事直接写s s[:i] s[i:ik][::-1] s[ik:]这样虽然能过但每轮循环都会创建多个中间字符串代码也不够干净。Python 相对推荐的做法是先转成list反转完再.join()回来。C 和 Go 则要友好得多可以直接在string或[]byte上原地交换。如果你在面试现场我的建议是先展示最简单、最容易证明正确的写法比如 Java 转char[]然后用一两句话补充说明这类语言字符串不可变所以需要一次 O(n) 的转换如果换成 C/Go 可以做到 O(1) 额外空间。面试官要的是你的思路和稳定性而不是你把 O(1) 空间优化成核心竞争力。4.4 自测用例清单这道题我建议维护一份自测用例清单每次写完代码至少跑一遍输入k期望输出测试意图abcdefg2bacdfeg标准用例覆盖完整分组和剩余不足2k但不少于kabcd2bacd恰好一组abcde3cbade剩余不足 2k但不少于 kabcdef4dcbaef验证前半段反转、后半段保留abc2bac最后一组不足 k 个全部反转2空串abcde1abcdek1 实际等于不反转abcde10edcbak 大于等于字符串长度整体反转这些用例覆盖了所有边界场景。把这份清单留在代码注释里以后回看的时候能帮你快速确认自己当初是怎么想的。5. 刷题之外的一点个人体会这道题和我写过的大多数算法题一样真正难的不是代码而是识别问题结构。我早期刷题时喜欢背模板反转字符串用双指针反转链表用三指针。结果一遇到反转字符串II这种组合题就傻眼不知道该套哪个模板。后来刷多了才明白模板只是特定数据结构下的一种实现方式真正该做的是先看清问题的结构这是一个线性序列需要按固定步长分组再对组内区间做反转。识别出这个结构之后不管是字符串、数组还是链表都可以用同一套思路去拆解。我现在的刷题习惯是每做一道新题先不急着写代码而是问自己三个问题——序列是什么结构分组规则是什么组内要对区间做什么操作这三个问题答出来写代码就变成了翻译工作。反转字符串II是这三个问题的完美训练题因为它的序列是数组形态但它的结构是分组反转形态和链表版的分组反转是亲兄弟。最后分享一个实用小技巧遇到这种带区间、带分组的题目先在草稿纸上画一个坐标轴把 i、ik、i2k、n 这几个关键点标出来。坐标轴画完边界条件基本就消灭了大半。我做这道题的时候就是靠这张图躲过了绝大多数越界错误。数据结构算法这条路没有捷径但找对参照物、建立自己的分析框架绝对能让你少走很多弯路。 
长河君 · 2026/10/13 20:34:26 · 阅读 1.2k 反转字符串II与链表分组反转：一类问题的通用解法框架
数据结构算法系列写到链表篇的时候我一直在琢磨怎么把反转这个话题讲透。很多人习惯性地把题目分成数组题、字符串题、链表题好像数据结构不同解法就必须完全不同。但刷到一定量之后你会发现真正决定解法的往往是问题结构而不是数据结构的形态。反转字符串II就是很典型的一道题它表面上是字符串题可它的核心套路和链表里的每k个一组反转链表几乎是同一个思路——按固定长度分组再对组内区间做反转。所以我特意把这道题放进链表篇做对照用一道题把字符串反转和链表反转两条线串到一起顺便把边界条件一次讲清楚。如果你是刚开始刷算法题或者正在准备面试这篇文章应该能帮你省不少时间。我会从题目规则拆解开始讲到完整可跑的代码再延伸到链表反转的实现最后把我在实际调试中踩过的坑列出来。跟着走一遍你收获的不只是这一道题的解法而是一类分组反转问题的通用框架。1. 反转字符串II是一道披着字符串外衣的分组反转题1.1 题目规则拆解不是反转整个字符串而是每隔 2k 反转前 k 个这道题在算法题库里的编号是541题目描述很简短但信息量不小给定一个字符串 s 和一个整数 k从字符串开头算起每计数至 2k 个字符就反转这 2k 个字符中的前 k 个字符。后面还有两条补充规则如果剩余字符少于 k 个则将剩余字符全部反转如果剩余字符小于 2k 但大于或等于 k 个则反转前 k 个字符其余字符保持原样。第一次看的反应往往是这不就是一个双指针交换吗但真动手写的时候你会发现每 2k 个字符这个分组条件才是关键。拿官网的经典示例拆一遍s abcdefgk 2。先看下标 0 到 3也就是 abcd这是完整的一组 2k 个字符。按照规则只反转前 k 个字符也就是反转 ab得到 ba所以第一组处理完变成 bacd。再看剩下的 efg总共 3 个字符。3 大于等于 k2但小于 2k4于是归入第二条规则只反转前 k 个字符也就是反转 ef得到 fe最后一个字符 g 保持不动。最终结果是 bacdfeg。再看一个 k3 的例子s abcdefghij。前 6 个字符 abcdef 是一组反转前 3 个变成 cbadef。剩下 ghij 一共 4 个字符4 大于等于 3 但小于 6所以反转前 3 个 ghi得到 ihg最后的 j 不动。最终结果是 cbadefhgji。这两个例子走完你应该能感觉到题目本身没有高深技巧真正的难点全在分组的边界和最后一组怎么处理上。而这恰恰是很多人写错的地方后面我会专门讲。1.2 为什么这道字符串题会出现在链表篇系列里我写这个系列时一直在强调一个观点数组、字符串支持随机访问定位区间只需要两个下标链表只能靠指针一步一步走定位区间要麻烦得多。但抛开访问方式的差异这两类题的内核完全一致——都是对一个线性序列按固定步长切块再对切出来的区间做反转操作。这个系列的链表篇前面已经讲过反转整个链表、反转链表的前 N 个节点指针操作的细节大家应该比较熟了。这时候放一道字符串题进来不是为了凑数而是想让大家看到同一个框架在不同数据结构上是怎么落地的。反转字符串II节奏是步长为 2k 分组反转组内前 k 个而链表题每 k 个一组反转链表节奏是按 k 个节点分组反转组内全部节点。两者都包含两层循环思维外层管分组移动内层管区间反转。很多面试题看起来吓人其实就是把这种熟悉的套路换了一个数据结构包装。你提前把这种分组反转的通用解法想明白面试时遇到变体题就从容得多。2. 核心思路先分组再反转组内区间2.1 i 2k 而不是 i k这是最容易写错的一行这个解法最核心的一行代码就是循环步长。我见过很多人第一次写这道题都写成i k理由是每组要反转前 k 个那处理完一组就前进 k 个位置。这个理由听起来合理其实是错的。建议你仔细想一下分组结构每一轮处理的是一个长度为 2k 的窗口窗口里前半段要反转后半段是原样保留的。所以处理完当前窗口之后下一轮的起点必须跳过整个窗口也就是向后移动 2k 个位置。如果只移动 k 个位置下一轮就会从上一轮保留的那 k 个字符开始把不该反转的内容又反转了一遍。举个例子s abcdefghijk 2。下标 0 到 3 是一组第一轮反转 ab 得到 bacd。如果下一步i 4下一轮从下标 4 开始处理 efgh这是正确的。但如果错误地写成i 2下一轮就从下标 2 开始把上一轮保留的 c、d 当成新一组的前半段去反转结果整个字符串会被搅得乱七八糟。所以最稳妥的写法就是for (int i 0; i n; i 2 * k) { // 处理以 i 开头的一组 }这一行想通整道题的框架就稳了。2.2 反转区间边界统一用 min(i k, n) 处理分组步长确定之后下一步是确定当前这一轮要反转的区间到底是从哪到哪。规则很清晰反转区间长度是 k起点是 i终点理论上是 i k - 1。但最后一组可能不足 k 个字符这时终点就变成了 n - 1。两个规则合并起来终点可以写成int right Math.min(i k - 1, n - 1);这里Math.min的作用是防止越界。当i k - 1大于等于n - 1时说明剩余字符不足 k 个终点自动收窄到 n - 1也就是把剩余字符全部反转。当i k - 1小于n - 1时说明这一组至少有 k 个字符正常反转前 k 个即可。如果你喜欢用开区间思维也可以写成这样int end Math.min(i k, n); // end 是反转区间的开区间右边界两种写法本质一样但开区间版本在配合substring或切片操作时更容易配对不容易出现差一错误。我个人的习惯是用开区间因为后面判断本组后半段从哪到哪时会更清晰。2.3 两种代码实现对比双指针版与 StringBuilder 版先看最朴素的双指针版本用 Java 实现。思想是把字符串转成字符数组然后对每个分组区间做头尾交换public String reverseStr(String s, int k) { char[] arr s.toCharArray(); int n arr.length; for (int i 0; i n; i 2 * k) { int left i; int right Math.min(i k - 1, n - 1); while (left right) { char tmp arr[left]; arr[left] arr[right]; arr[right] tmp; left; right--; } } return new String(arr); }这个版本最贴近题目本质每一步都在做定位区间 双指针交换。代码量少也不容易被 StringBuilder 的切片逻辑绕晕。我建议面试时优先写这个版本思路一眼就能讲清楚。再看一个用 StringBuilder 的版本。它的思路是逐个处理分组前 k 个字符反转后追加后 k 个字符如果有原样追加public String reverseStr(String s, int k) { StringBuilder sb new StringBuilder(); int n s.length(); for (int i 0; i n; i 2 * k) { int mid Math.min(i k, n); // 本组要反转部分的结束位置开区间 StringBuilder sub new StringBuilder(s.substring(i, mid)); sb.append(sub.reverse()); // 反转前 k 个 int restEnd Math.min(i 2 * k, n); // 本组后半段的结束位置开区间 if (restEnd mid) { sb.append(s.substring(mid, restEnd)); // 后半段原样保留 } } return sb.toString(); }这个版本在理解开区间时会稍微费一点脑子但好处是代码结构非常贴合题目描述先反转前 k 个再保留剩下的。两种实现我都跑过结果一致。个人建议是如果面试官让你实现优先写字符数组版如果是日常刷题可以用 StringBuilder 版加深对区间的理解。2.4 复杂度分析与极值测试时间复杂度是 O(n)因为每个字符最多被访问两次一次是确认为当前窗口的前半段或后半段另一次是在反转时被交换。无论哪种实现都没有嵌套的多重循环所以线性复杂度是确定的。空间复杂度需要注意语言差异。Java 的 String 是不可变的转成char[]本身就是 O(n) 的额外空间。StringBuilder 版本里substring会创建新的字符串累计空间也是 O(n)。如果是在 C 里直接对string原地操作或者 Go 里对[]byte原地操作额外空间可以是 O(1)。这一点在面试时主动说出来能体现你对语言特性的了解。提交代码之前建议先用几个极值测试自测k 1 时反转前 1 个字符等于不反转结果应该和原字符串一致k 大于等于字符串长度时整个字符串应该被反转空字符串应该直接返回空串。这几个用例能帮你把大多数边界错误挡在提交之前。3. 把字符串反转的思路迁移到链表上3.1 为什么链表不能像字符串那样用双下标字符串反转的核心是任意位置都能 O(1) 访问所以两个下标一前一后往中间靠拢交换元素就行。链表不行你要访问第 j 个节点只能从头部开始逐个 next定位成本是 O(j)。想在链表上反转一个区间不能靠下标交换只能靠改变节点之间的指向。打个比方一排人面朝右站现在要让他们全部面朝左。数组的做法是让最左边的人和最右边的人互换位置效率很高链表却是每个人只有一条手搭在前面一个人肩膀上你要让整排人转身只能从一端开始一个一个把手的朝向调过来。这就是为什么链表的反转代码里全是prev、curr、next这三个指针。理解了这个差异你再看链表反转代码就不会觉得是在背模板了——它只是在顺着链表的结构特性做事。3.2 反转整个链表三指针迭代法与递归法先看最基础的迭代反转。假设链表是 1 - 2 - 3 - 4 - null目标是变成 4 - 3 - 2 - 1 - null。public ListNode reverseList(ListNode head) { ListNode prev null; ListNode curr head; while (curr ! null) { ListNode next curr.next; // 先保存下一个节点否则改动 curr.next 后会丢失 curr.next prev; // 掉转当前节点的指针方向 prev curr; // prev 前进 curr next; // curr 前进 } return prev; }每一步走一遍你就明白了初始 prev 是 nullcurr 是节点 1。第一轮先把 next 存成节点 2然后让 1.next null此时节点 1 变成了尾节点接着 prev 节点 1curr 节点 2。第二轮让 2.next 节点 1prev 变成节点 2curr 变成节点 3。这样一轮一轮下去原头节点 1 的 next 最终指向 null新的头节点 4 被返回。这里有一个细节值得注意第一次迭代就把head.next设成了 null。这正是反转后的尾节点该有的样子如果不做这一步链表里会出现环。递归版本也很经典思路是假设当前节点的后面已经被反转好了我只需要把自己接到这段反转链表的末尾public ListNode reverseList(ListNode head) { if (head null || head.next null) { return head; } ListNode newHead reverseList(head.next); head.next.next head; // head.next 此时是反转后的尾节点 head.next null; // 当前节点变成新的尾节点 return newHead; }递归版代码更短但对新手来说有点绕。我建议先把迭代版写熟练再回过头来看递归版两个都掌握之后遇到反转区间链表这种进阶题会轻松很多。3.3 每 k 个一组反转链表分组反转思想的链表落地现在回到正题如果把这个分组反转思想放到链表上就是题库里另一道名题每 k 个一组反转链表。先看一下这道题的要求给定一个链表每 k 个节点一组进行反转最后一组如果不足 k 个节点则保持原样。这和字符串版的规则几乎一一对应只不过字符串版是每 2k 个字符一组反转前 k 个而链表版是每 k 个节点一组反转整组。实现需要几个辅助指针。我用一个 dummy 节点来避免对头节点做额外判断然后不断重复走 k 步检查够不够 - 反转当前组 - 接回原链表这个过程public ListNode reverseKGroup(ListNode head, int k) { ListNode dummy new ListNode(0); dummy.next head; ListNode pre dummy; // pre 始终指向上一组的尾节点 ListNode tail dummy; // tail 用来探路判断当前组是否够 k 个 while (tail.next ! null) { // 1. tail 先走 k 步如果走到 null 说明剩余不足 k 个 for (int i 0; i k tail ! null; i) { tail tail.next; } if (tail null) { break; // 剩余节点不足一组保持原样返回 } ListNode start pre.next; // 当前组的第一个节点 ListNode nextGroup tail.next; // 下一组的第一个节点 // 2. 把当前组从原链表中切出来单独反转 tail.next null; pre.next reverseList(start); // 3. 反转后 start 变成了当前组的尾节点把它接回下一组 start.next nextGroup; // 4. 移动 pre 到当前组的尾节点准备下一轮 pre start; tail pre; } return dummy.next; }这里的reverseList就是前面写的迭代反转函数。因为我们在反转前已经用tail.next null把当前组切成了独立链表所以reverseList(start)只会反转这一组内部的指针关系。把这道链表题和字符串题放在一张表里对照很多抽象的东西一下就清晰了维度反转字符串II每k个一组反转链表分组步长每 2k 个字符一组反转前 k 个每 k 个节点一组反转整组区间定位下标 i k用 min 防止越界tail 指针先走 k 步探路反转手段双指针头尾交换字符prev/curr/next 三指针改指向连接方式后半段原样保留天然拼接需要把组尾手动接到下一组开头最后一组不足 k 个全部反转不足 k 个保持原样我写代码的时候经常把这张表默背一遍确认自己当前写的是哪个版本。一旦混了比如在字符串题里把不足 k 个当成保持原样一提交就会有反例直接教你做人。4. 实战中的高频错误与避坑建议4.1 循环步长写错全盘错乱的典型样例前面反复强调的i 2k我还是要单独拿出来说一次因为这个错的隐蔽性确实高。我见过不少基础不错的同学思路完全正确代码写到循环那行手一滑就写成i k然后对着错误用例看半天怎么也想不通。给你一个直观的错误样例。s abcdefghijk 2正确结果是 bacdfe hgij 格式当然是 bacdfehgij。如果步长错误地写成加上 k也就是 2过程会是这样i0 反转 abi2 时因为上一轮保留了 cd现在又从 c 开始反转 cd得到 dci4 反转 ef等等。最后你会发现偶数位的字符几乎都被翻转了一次整个字符串面目全非。所以提交前先花十秒钟心算一个小例子确认循环变量的跳法是 2k。这个习惯成本极低收益极高。这里我不妨说得再直接一点我自己的经验是这道题只要循环步长写对边界用 min 包一下基本就没有什么压轴坑了。4.2 最后一组的两条规则不能混为一谈很多人在剩余字符不足 2k 但不少于 k和剩余字符少于 k这两种场景之间犯迷糊。前者要只反转前 k 个后者要全部反转。如果你用right Math.min(i k - 1, n - 1)这个公式两个场景会被自动区分如果剩余字符大于等于 k那么i k - 1一定小于n - 1min 会取前者正好只是反转前 k 个。如果剩余字符少于 k那么i k - 1会超过n - 1min 会取后者相当于把剩下的字符全部反转。一句话不要写两个 if 去分支统一用一个 min 就能覆盖全部情况。这是我处理区间问题时最常用的技巧遇到不确定边界的时候优先想怎么用一个上界约束写出来而不是不停加条件分支。4.3 语言特性带来的原地反转陷阱还有一个细节容易被忽略不同的语言里字符串的可变性差别很大这会直接影响你写法的选择。Java 的 String 不可变你必须先转char[]或者用StringBuilder才能修改。Python 的字符串也不可变很多新手图省事直接写s s[:i] s[i:ik][::-1] s[ik:]这样虽然能过但每轮循环都会创建多个中间字符串代码也不够干净。Python 相对推荐的做法是先转成list反转完再.join()回来。C 和 Go 则要友好得多可以直接在string或[]byte上原地交换。如果你在面试现场我的建议是先展示最简单、最容易证明正确的写法比如 Java 转char[]然后用一两句话补充说明这类语言字符串不可变所以需要一次 O(n) 的转换如果换成 C/Go 可以做到 O(1) 额外空间。面试官要的是你的思路和稳定性而不是你把 O(1) 空间优化成核心竞争力。4.4 自测用例清单这道题我建议维护一份自测用例清单每次写完代码至少跑一遍输入k期望输出测试意图abcdefg2bacdfeg标准用例覆盖完整分组和剩余不足2k但不少于kabcd2bacd恰好一组abcde3cbade剩余不足 2k但不少于 kabcdef4dcbaef验证前半段反转、后半段保留abc2bac最后一组不足 k 个全部反转2空串abcde1abcdek1 实际等于不反转abcde10edcbak 大于等于字符串长度整体反转这些用例覆盖了所有边界场景。把这份清单留在代码注释里以后回看的时候能帮你快速确认自己当初是怎么想的。5. 刷题之外的一点个人体会这道题和我写过的大多数算法题一样真正难的不是代码而是识别问题结构。我早期刷题时喜欢背模板反转字符串用双指针反转链表用三指针。结果一遇到反转字符串II这种组合题就傻眼不知道该套哪个模板。后来刷多了才明白模板只是特定数据结构下的一种实现方式真正该做的是先看清问题的结构这是一个线性序列需要按固定步长分组再对组内区间做反转。识别出这个结构之后不管是字符串、数组还是链表都可以用同一套思路去拆解。我现在的刷题习惯是每做一道新题先不急着写代码而是问自己三个问题——序列是什么结构分组规则是什么组内要对区间做什么操作这三个问题答出来写代码就变成了翻译工作。反转字符串II是这三个问题的完美训练题因为它的序列是数组形态但它的结构是分组反转形态和链表版的分组反转是亲兄弟。最后分享一个实用小技巧遇到这种带区间、带分组的题目先在草稿纸上画一个坐标轴把 i、ik、i2k、n 这几个关键点标出来。坐标轴画完边界条件基本就消灭了大半。我做这道题的时候就是靠这张图躲过了绝大多数越界错误。数据结构算法这条路没有捷径但找对参照物、建立自己的分析框架绝对能让你少走很多弯路。