1. 为什么很多人栽在LeetCode 25这道题真正考的并不是反转刷到LeetCode 25「K个一组翻转链表」之前很多人其实已经能把反转链表、两两交换写得挺顺了。但到了这道题突然就卡住反转我会啊K个一组我也懂啊怎么拼在一起就不对说实话这个题是链表题目里的分水岭它真正考你的不是能不能写出反转而是你能不能把一个连续的动作按组切分成可独立执行的单元再把这些单元安全地串回一条完整的链。先看题目要求给你一个链表每K个节点一组进行翻转最后不足K个的保持原顺序。这里的难点藏在两处。第一每K个一组意味着你脑子里不能只有头节点的概念必须同时管住每一组的前驱、头、尾、下一组的头这四个位置漏掉任何一个链表就会断在中间。第二不足K个不翻转这个条件需要在循环或递归的每一轮开始前做一次长度判断——这个判断写错要么把最后一小段也翻了要么整条链根本走不到终点。很多人的失败路径是直接套用单链表反转的代码然后在外层套一个while结果发现反转完一组之后找不到下一组的位置了。这是典型的工具正确、方法错误——你把整条链的反转函数用在一个子段上它会把子段之后的所有节点全部卷进去这就是断链的最常见原因。所以我在本文反复提示一个关键认知这道题的核心操作不是反转链表而是reverse N——精确地反转前N个节点并且让反转后的尾巴恰好停在下一组的入口不多吞一个节点也不少连一个节点。这篇文章的结构也围绕这条主线展开先讲清楚为什么反转整条和反转前N个是两个难度级别再给出分组的心智模型最后分别用递归和迭代把它落地。我会把边界条件和断链现场单独拿出来讲因为我把这些年刷题、面试、看别人代码的典型翻车姿势都汇聚在这里。不管你是准备面试还是想彻底吃透链表操作顺着这条主线走应该能比单纯背答案多得一些真正的掌控感。2. 地基工程从反转整条链表到「反转前N个」差别只在一条指针要理解LeetCode 25得先确认地基稳不稳。链表反转这个动作本身不复杂但很多人的代码只是背下来了并没有真正理解每一步指针的移动规律。这里先把最基础的单链表反转写出来然后在此基础上升级出反转前N个的两种形态。2.1 基础操作三指针迭代反转整条链表def reverse_list(head): prev None curr head while curr: nxt curr.next curr.next prev prev curr curr nxt return prev这段代码的核心思路用一句话说就是每走一步把当前节点的next从后面的节点改成前面的节点。prev先指向None表示新链表的终点curr从head出发nxt暂存curr原本的下一个节点防止改完next之后找不到路然后prev和curr整体右移。循环结束时prev恰好停在原链表的最后一个节点上也就是新链表的头。这个函数没问题但它有一个隐含的坏毛病它会把整条链从头反转到None为止。如果你只打算反转前半段它会把后半段也一并卷走。所以在K个一组翻转的场景里绝对不能直接把这个reverse_list用在子段上除非你先手动切断子段与后续节点的连接。这个切断的需求就是引出reverse N概念的开关。2.2 第一次升级反转前N个并把尾巴接回第N1个节点现在需求变了只反转前N个节点后面的节点原封不动。例如链表1 - 2 - 3 - 4 - 5N3目标是3 - 2 - 1 - 4 - 5。这时你会发现代码和reverse_list很像只是在收尾时多了一步需要找到原来的第N1个节点curr并把反转后的尾部也就是原来的head接到它身上。def reverse_first_n(head, n): prev None curr head for _ in range(n): nxt curr.next curr.next prev prev curr curr nxt head.next curr # head现在是反转段的尾部把它和后续链表接上 return prev这里最关键的一行是head.next curr。循环结束后curr刚好站在第N1个节点上如果链表的长度恰好等于N那curr就是None。head经反转后已经变成这段子链的最后一个节点只有把它的next指向curr才能保证后面的节点保持原顺序。这一步是反转整条和反转前N个的本质区别——你必须明确告诉这段子链你的尾巴连向哪里。提示这里的隐藏前提是调用前必须确定head之后至少有N个节点。在LeetCode 25的主函数里我们会先做数K步的判断确认数量够再调用这个函数所以可以放心。2.3 第二次升级以边界节点收尾的tail-bounded reverse上面reverse_first_n的写法已经能够完成K个一组翻转但还有一个更优雅的变种我强烈建议你掌握因为它能让你彻底摆脱切断与重接的额外操作。思路很简单既然已经知道第N1个节点是谁不如直接把它作为反转的边界传进去。def reverse_between(head, tail): prev tail # prev从边界节点开始而不是从None开始 curr head while curr ! tail: # 走到边界就停 nxt curr.next curr.next prev prev curr curr nxt return prev这个函数反转区间[head, tail)注意tail本身不参与反转它是下一组的起点。为什么prev要从tail开始因为第一个被反转的节点是head它的next会被改成prev而prev初始时正好指向tail这一改就天然完成了反转后的尾巴指向下一组起点的连接。后面每处理一个节点都是同样的逻辑直到curr走到tail停止。最终返回的prev是反转后的新头。对比一下你就明白了reverse_first_n需要在循环结束后额外写一行head.next curr而reverse_between把这一步化进了prev tail的初始化里。这个在LeetCode 25里可以少写一行容易错的代码。我之前面试时问过不少候选人大多数都能写出第一种但第二种能顺手写出来的人说明是真的理解了反转一个子段的边界本质。所谓reverse N的成熟形态就是让反转操作在正确的边界处停止并让边界两侧的指针关系保持完整。3. 分组心智模型每一轮循环只要做四件事在写递归或迭代代码之前先把K个一组翻转的整体流程在脑子里过一遍。我建议把每一组的处理抽象成四件事数出K步、暂存后继、反转子段、重接前后。用个生活化的类比想象一列火车有若干节车厢现在要按每K节一组重新编组每组内部的车厢顺序倒过来排但组与组之间的顺序不变。你要做的其实是先数出这一组有几节车把队伍从第K1节那里拦腰断开让这一组的车厢原地掉头然后再把掉头后的组拼回整列火车。对应到链表操作每一轮需要盯住的节点有四个pre 上一组的最后一个节点 start 本组的第一个节点 end 本组的最后一个节点 next_group 下一组的第一个节点比如链表1 - 2 - 3 - 4 - 5 - 6 - 7K3。第一组里start1end3next_group4。反转完第一组链表变成3 - 2 - 1 - 4 - 5 - 6 - 7。此时pre变为原来的start也就是新的1节点它是上一组的尾部第二组的start4end6next_group7。反转后变成6 - 5 - 4 - 7。第三组只有一个节点7不足K个保持原序。这个模型的强大之处在于所有组都遵循同一套规则唯一需要单独处理的只有不足K个这个终止条件。判断方法很朴素从当前起点出发尝试走K步走不到第K步就遇到了None说明剩余节点不够一组直接收尾。这个判断在递归版和迭代版里几乎一样只是放的位置不同。接下来我分别给出递归版和迭代版的完整实现。两者共享同一个子段反转的函数区别只在于如何处理组与组之间的推进递归靠函数调用的参数传递自动推进迭代靠手动维护pre指针推进。4. 递归实现先反转当前组再把后续直接交给函数自己递归版很推荐作为第一个能跑通的版本因为它的代码结构非常短而且思路高度贴合分组这个概念。核心想法先数出K个节点如果不够K个直接返回head如果够K个就反转这K个节点然后把从这个K个节点之后的部分递归处理最后把两段接起来。4.1 完整代码class Solution: def reverseKGroup(self, head: Optional[ListNode], k: int) - Optional[ListNode]: cur head cnt 0 while cur and cnt k: cur cur.next cnt 1 if cnt k: return head new_head self.reverse_between(head, cur) head.next self.reverseKGroup(cur, k) return new_head def reverse_between(self, head, tail): prev tail curr head while curr ! tail: nxt curr.next curr.next prev prev curr curr nxt return prev4.2 逐段拆解四个步骤各司其职第一步cur从head出发走K步。循环退出时有两种可能要么cur变成了None说明head后面不足K个节点要么cur恰好指向第K1个节点。如果cnt k说明这一组凑不满按照题目要求保持原序直接返回head即可。这里有一个很容易疏忽的细节cnt k的判断不能省否则当剩余节点不足时你依然会对一个短子段强行反转返回的新头会让整条链错乱。第二步调用reverse_between(head, cur)反转[head, cur)这一段。前面已经讲过这个函数把prev初始化为cur所以反转完之后原head现在变成了这一段的新尾巴会自动指向cur。这省去了手工连接尾部与下一组的操作。第三步head.next self.reverseKGroup(cur, k)。这一行是递归版的精华。head是当前组反转后的末尾它现在虽然已经指向了cur但cur之后还没处理。递归调用传进去的参数cur正是下一组的起点。递归返回后下一组内部已经完成翻转返回值是下一组的新头把它接到当前组的末尾上。如果你把这行误写成new_head.next self.reverseKGroup(cur, k)就会丢掉new_head这个头部因为new_head是当前组反转后的头它应该作为整条结果链的进入点返回给上层而不是挂在下面当尾巴。第四步返回new_head也就是当前组反转后的新头。对于最外层调用来说这就是整条链表翻转后的头节点。整个递归过程像接力棒一样每一层只负责自己的K个节点剩下的交给下一层最终一层一层接回来形成完整链表。4.3 用一个具体例子走一遍递归拿1 - 2 - 3 - 4 - 5K2来演算。第一层cur走两步指向3。调用reverse_between(1, 3)把1 - 2反转为2 - 1此时1.next指向3。然后调用self.reverseKGroup(3, 2)处理3 - 4 - 5。第二层从3出发走两步cur指向5。调用reverse_between(3, 5)把3 - 4反转为4 - 33.next指向5。再调用self.reverseKGroup(5, 2)处理5。第三层从5出发走两步但只走一步就碰到Nonecnt 2直接返回5。回到第二层第三层返回5于是3.next 5本层返回4。回到第一层第二层返回4于是1.next 4本层返回2。最终结果2 - 1 - 4 - 3 - 5和题意完全一致。注意第三层只返回了5因为它不足K个保持原序。如果你把这个例子自己动手画一下指针箭头的变化对递归的理解会深很多。4.4 递归版的时间与空间复杂度时间复杂度是O(n)因为每个节点最多被访问两次一次在数K步的循环里被cur经过一次在被反转时被curr经过整体是线性扫描。空间复杂度方面递归深度等于组的数量大致是n/k层每层只有常数个变量所以空间O(n/k)。最坏情况下如果K接近1深度会退化为O(n)。这在实际工程里通常没什么问题但如果面试官明确要求O(1)空间你就需要切到迭代版。5. 迭代实现哨兵节点加pre指针把每一组串成流水线递归版虽然清晰但很多面试官会追问一句你能用迭代写吗迭代版的优势是空间O(1)而且代码执行更直接。代价是你必须手动管理一个哑元节点dummy并且每一步的指针更新都不能乱。5.1 完整代码class Solution: def reverseKGroup(self, head: Optional[ListNode], k: int) - Optional[ListNode]: dummy ListNode(0) dummy.next head pre dummy while True: end pre for _ in range(k): if end.next is None: return dummy.next end end.next start pre.next next_group end.next end.next None pre.next self.reverse_list(start) start.next next_group pre start def reverse_list(self, head): prev None curr head while curr: nxt curr.next curr.next prev prev curr curr nxt return prev5.2 为什么必须先有一个dummy哨兵节点链表的第一个节点没有前驱翻转第一组时你需要把新头挂回某个位置。如果直接用head指针第一组翻转后head到底指向谁是模糊的。dummy节点的作用就是给整个链表一个统一的前驱让所有组都遵循同一套处理逻辑本轮翻转后把结果挂在pre.next上。最后返回dummy.next才拿到真正的链表头。哨兵节点这个技巧在链表题里极其常用。不只是K个一组翻转凡是要操作链表头部、或者头节点可能变化的问题先加一个dummy都能省掉大量的特殊判断。面试时说出用dummy统一头节点的边界处理本身就是加分项。5.3 每轮循环的四步操作第一步从pre出发走K步找end。这里的pre初始是dummy走K步之后end指向第一组的最后一个节点。如果中途end.next已经是None说明剩余节点不足K个此时整条链表已经处理完毕返回dummy.next。为什么不是走完K步再判断因为如果链表刚好只剩K个节点end会走到最后一个节点上end.next为None这属于正好够一组的合法情况也应该翻转所以判断必须在下一步之前进行但必须在for循环的每一次检查end.next理由留到下一条再讲。第二步记录start pre.next和next_group end.next然后把end.next置为None。这一步容易被忽略但它非常关键。start是本组第一个节点也是反转后将成为本组最后一个节点的节点next_group是下一组的头。end.next None的作用是隔离本组让接下来调用的reverse_list只作用于[start, end]这一段。如果没有这行reverse_list会沿着end.next一路反转下去把下一组甚至后面所有组都吞进去最终链表变成一团乱麻。第三步pre.next self.reverse_list(start)。reverse_list返回反转后本组的新头也就是原来的end。挂到pre.next上相当于接通了上一组与本组的连接。此时start变成了本组的尾巴且它的next是None因为上面断开了。第四步start.next next_group把本组尾巴和下一组的头接上。到这里这一组才算完整地焊回了链表。最后更新pre start因为start现在是本组的最后一个节点对下一组来说它正是上一组的尾部。你可能已经注意到每轮循环重复的动作完全一致不会因为位置不同而改变。这就是迭代版的漂亮之处dummy pre指针让所有组看起来都一样。5.4 迭代和递归怎么选从我自己的刷题经验来看第一遍理解用递归更快但最终上考场或者面试手写我优先写迭代。原因有三一是迭代空间O(1)面试官不用为递归栈的深度操心二是迭代的执行路径是直线型的不容易因为递归层数太深而晕三是面试中面试官经常在迭代代码基础上提问如果尾段不足K也要翻转怎么办、能不能只改一行实现某种变体迭代的改动点更集中。但递归也值得掌握因为它能锻炼你把规模缩小的问题扔给函数自己的思维方式这种思维在其他链表递归题里非常有用。如果你时间有限我建议至少做到看着题目的输入能立刻写出迭代版并且能解释清楚每一行指针操作的意图。6. 边界条件与断链现场最常见的五个错误和排查思路代码写对一遍不算本事能自己排查断链才是真正理解。下面我把K个一组翻转最常见的几个错误场景整理出来每个都对应一段真实的踩坑经历。6.1 错误一迭代版忘记断开end.next下一组被整段吞掉这个坑我见过太多次了。把end.next None注释掉跑测试时你会发现链表后面所有的组全部被反转了而且结果链出现环形引用最终打印链表时会死循环或报错。原因前面说过reverse_list是反转整条链的工具它会一直走到None才停如果end.next还连着下一组它自然把下一组也算进去了。排查思路很简单在调用reverse_list之前打断点看start到end这段的长度是不是恰好K个如果长度超过K多半就是没断开。修复就是补上end.next None这一行没有别的花样。6.2 错误二递归版里把head.next错写成new_head.next递归版最经典的手误。很多人在第三步会不假思索地写new_head.next self.reverseKGroup(cur, k)理由是新头后面应该接递归处理的结果。这一写当前组的新头就被扔到了链表深处整个链表从第一组开始就缺了头返回结果自然不对。我建议在递归版里始终记住一句话new_head是结果head现在是尾巴。上层需要拿到的是这一组翻转后的头也就是new_head而head作为尾巴它的next要接上后续处理完的链表。先想清楚这两个指针的新身份再写赋值语句就不会犯这个错。6.3 错误三不足K个的末尾被无差别翻转稍微改一下题目要求比如不足K个也翻转实现上很简单把递归版中if cnt k: return head去掉或者把迭代版中的if end.next is None: return dummy.next改成某种强制翻转的逻辑。但如果题目要求的是不足K个保持原序而你忘了这个终止条件末尾就会被翻乱。这里我提供一个调试技巧写一个print_linked_list(head)函数每处理完一组就打印一次当前链表状态。运行一个小规模输入比如1-2-3-4-5K2如果打印出来末尾是1 - 4而不是1 - None说明指针重接有问题如果末尾变成3但顺序不对说明终止条件有误。通过打印状态来定位比盯着代码空想高效得多。6.4 错误四k1导致递归栈溢出或无效循环K1时每个节点单独成组翻转一个节点等于什么都不做。结果应该直接返回原链表。递归版对这个case也能工作但会无意义地递归N层浪费空间。迭代版走K步检查时end从pre出发因为pre.next存在能走一步end start然后反转单节点逻辑上没错只是空转一轮。如果你在意极端性能可以在函数开头加一行if k 1: return head。这不算特殊处理而是一个合法的剪枝面试时主动写出来能体现你对边界条件的敏感度。6.5 错误五空链表和单节点链表的静默失败空链表即head为None此时任何K的取值都不应该报错。迭代版里dummy.next head然后pre从dummy出发走K步时第一步就会遇到end.next is None直接返回dummy.next也就是None正确。但如果你没有用dummy直接操作head空链表会带来一堆额外的空指针判断。这也是为什么我特别推荐dummy写法。单节点链表、K1直接返回该节点K1也返回该节点。用上面的代码跑一遍都能通过。如果发现某些case特别容易出错我建议列一个快速自测清单空链表、单节点、K1、K等于链表长度、K大于链表长度、链表长度恰好是K的整数倍。这个清单在面试前花两分钟过一遍比反复通读代码更让人安心。7. 面试延伸从两两交换到任意区间反转的底层能力LeetCode 25不是孤立的一道题它和你刷过的其他链表题目如LeetCode 24、LeetCode 92共享同一套底层能力。如果你把本文的reverse_between彻底吃透后面几个变体基本是顺手的事。先说LeetCode 24两两交换相邻节点。这就是K2的K个一组翻转。你可以把K2代入上面的递归版或迭代版跑一下会发现结果完全正确。这也算是一种用通用解干掉特例的验证方法。面试时如果先被问到两两交换你可以说这道题等价于K2的K个一组翻转然后直接给出本文的迭代代码会让面试官对你的抽象能力印象不错。再说LeetCode 92反转从位置left到right的若干节点。这道题的思路其实也是分组反转的变体先把链表切成三段中间那段用reverse_between反转然后把三段接回去。很多人在92上头疼原因和25是一样的——搞不定反转一段之后怎么把前后接上。如果你已经理解了reverse_between的边界设计92的代码其实就是额外维护两个指针非常直观。还有一个面试官很喜欢改的条件如果末尾不足K个也要求翻转怎么改递归版删掉if cnt k: return head即可迭代版需要在不足K个时仍然把start到链表末尾这一段反转。不要小看这个改动它考察的正是你对终止条件和边界的理解。我个人在实际刷题中的体会是链表题的价值不在于写出某一道题的答案而在于把指针边界感训练出来。所谓边界感就是你看到一段子链时能立刻说出它的前驱是谁、后继是谁、反转之后谁是新头谁是尾巴。LeetCode 25恰好把这些要素全部揉在一起所以我才劝你不要只背答案而是把reverseN这个子能力单独拆出来练习。它不是一道题的技巧而是一类题的地基。最后再分享一个我常用的扩展练习在纸上画出1 - 2 - 3 - 4 - 5 - 6 - 7K3的完整指针变化过程每完成一组反转就画一张图。画完三张图你会发现自己对链表指针的掌控力有明显的提升——这比多刷十道同类题更管用。