★ FEATURED ARTICLE 先说个真实场景。我认识的一位开发者第一次在在线刷题平台遇到“链表中的节点每k个一组翻转”这道题时第一版代码写了大概四十行自测三个用例全过结果一提交就超时再一查发现是死循环。第二版终于不超时了但边界用例又错最后不足 k 个的节点被翻转了题目明明写着“保持原有顺序”。他后来跟我复盘时说这题看着只考一个“局部翻转”实际上处处都是陷阱指针保存的时机、组间衔接的顺序、长度不足 k 的兜底逻辑每一处都能写错。这篇文章我想把这道题彻底讲透。读者可以是刚接触链表的小白也可以是准备面试刷题的中级开发者甚至是你临时需要给团队讲链表题时的参考资料。我会从题目本身开始把迭代和递归两种解法都拆开揉碎再把最容易踩的边界条件列成清单最后聊聊这题背后的工程思维——为什么“分组处理”这种模式在真实系统里到处都是。1. 题目到底在问什么从示例拆解容易被漏读的规则1.1 题目还原输入输出示例题目描述通常是这样一句话给你一个链表每 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]第一组里链表被分成 [1,2]、[3,4]、[5] 三组前两组各自翻转最后一组只有 1 个节点不足 2 个保持原样。第二组里[1,2,3] 翻成 [3,2,1]剩下 [4,5] 不足 3 个保持原样。这里要特别提醒新手链表翻转是“节点整体”的翻转包括节点里的值和它的 next 指向不是只把值倒过来。有些初学者图省事想把每组的 val 用数组收集后再倒序写回这在小规模数据上看起来能过但面试官一眼就能看穿——题目考察的就是指针操作这么做等于没做。1.2 三条潜规则缺一条都会做错这题之所以容易翻车是因为题目文字里藏着几个没说死但必须遵守的潜规则。第一条最后不足 k 个节点要保持原有顺序。这意味着你不能把整个链表都翻转一遍然后再假设最后一组反着接回去就行。比如 [1,2,3,4,5]k3结果是 [3,2,1,4,5]而不是 [3,2,1,5,4]。很多错误代码就栽在这。第二条k 可以等于 1也可以等于链表的整个长度还可以大于链表长度虽然题目说 k 小于等于长度但实现时空链表、k1 这类情况都要考虑。k1 时每组只有一个节点翻转等于没翻链表应该原样返回。如果代码里 for 循环处理 k 步时指针走错了这种最简单的情况反而会直接崩。第三条翻转后链表的头节点可能变化。原始 head 不一定是新链表的头。比如 [1,2,3]k2翻转后是 [2,1,3]新链表的头是原来的第二个节点。如果你最后 return head结果永远不对。这也是为什么迭代解法里几乎都要引入一个虚拟头节点我们后面细说。1.3 为什么点名“链表的节点”而不是“链表的值”再深入一层题目要求翻转“节点”不是翻转“值”。链表的每个节点在内存里是一个对象有自己的地址。翻转节点意味着改变每个节点的 next 指针方向让原来指向后面的节点改指向前面的节点最终整组节点的排列顺序倒过来。举个例子链表 [1,2,3] 翻转后节点 2 的 next 要从指向 3 变成指向 1节点 1 的 next 要从指向 2 变成指向 None。如果你只交换节点里存的数值内存中的节点关系完全没变等于什么都没做。这在工程上也有意义真实业务里链表节点往往不只是存一个数字可能存一整条业务数据记录。代码想交换记录里的所有字段是笨办法改指针才是链表操作的灵魂。2. 这题为什么高频出现指针操作的心智模型是关键2.1 链表操作的本质改 next 指针值无法搬动先说为什么这道题在各类面试里出现频率那么高。数组翻转大家都写过直接双指针首尾交换简单直白。但链表不能按下标访问你只能从一个节点通过 next 走到下一个节点所以翻转链表时必须手动维护一组指针让它们像“履带”一样一格一格推进。链表操作的核心心法是一切操作都体现在 next 指针的变化上。插入节点是先把新节点指向后继再把前驱指向新节点删除节点是让前驱直接越过被删节点翻转链表则是把所有 next 全部掉头。理解了这一点你再看任何链表题都会感觉它们是同一类问题——只是指针数量和维护时机不同。做链表题还有个物理习惯必须养成画图。不要嫌麻烦一支笔一张纸把节点画成方框把 next 画成箭头每改一步就在图上更新箭头。我见过太多人一上来就写代码结果指针指错方向DEBUG 半小时眼睛都快瞎了。链表操作里“脑子里有图”比“脑子里有代码”重要得多。2.2 一次翻转的微观过程三指针走位我们先看最基础的子问题给一个单链表的头节点翻转整条链表。这也是“每 k 个一组”题里的最小操作单元。假设链表是 1 - 2 - 3 - None我们要得到 3 - 2 - 1 - None。标准做法是用三个指针 prev、cur、next。prev None cur head while cur is not None: nxt cur.next # 先保存下一步要去的节点 cur.next prev # 把当前节点的指针掉头 prev cur # prev 往前走 cur nxt # cur 往前走 return prev第一次循环cur 是节点 1先把 nxt 记成节点 2再让节点 1 的 next 指向 None然后 prev 变成节点 1cur 变成节点 2。第二次循环保存 nxt 为节点 3让节点 2 的 next 指向节点 1prev 变成节点 2cur 变成节点 3。第三次循环nxt 为 None让节点 3 的 next 指向节点 2prev 变成节点 3cur 变成 None。循环结束返回 prev也就是节点 3。注意每一步里 nxt 的作用它是“还没处理的后续链表的入口”。如果不提前保存一旦执行 cur.next prev后面的链表就丢了再也找不回来。这个“先保存再改指针”的意识正是整个链表操作里最值钱的习惯。2.3 组与组之间的接缝才是真正的分水岭单链表翻转是热身每 k 个一组翻转的真正难点在于你要把链表切成若干段每段内部翻转段与段之间还要重新接起来。举个例子链表 [1,2,3,4,5]k2。第一组是 [1,2]翻完变成 [2,1]第二组是 [3,4]翻完变成 [4,3]。可如果只是简单地把两组翻转结果拼起来顺序是 2 - 1 - 4 - 3 - 5但这要求节点 1 的 next 必须指向节点 4而不是原来的节点 3。关键在于第一组翻转完成后原本属于第一组的尾节点节点 1翻转后变成了尾需要指向第二组翻转后的头节点节点 4。也就是说你必须先完整处理第二组拿到第二组的新头再回头来改第一组尾节点的 next。这个“先处理后组、再连接前组”的顺序在迭代里体现为“先保存下一组入口”在递归里体现为“先递归到底再逐层接回”。不理解这一层代码就会写成断链状态。3. 迭代解法一虚拟头节点 局部翻转函数3.1 为什么需要一个 dummy 节点迭代解法的第一步是创建一个虚拟头节点也叫哨兵节点。代码通常这么写dummy ListNode(-1) dummy.next head你可能会问为什么不直接操作 head原因是链表的头节点在翻转后可能变化。比如 [1,2,3]k2最终结果是 [2,1,3]原来的 head 是节点 1现在真正的头是节点 2。如果你从头到尾都用一个“前驱指针 pre”去记录每组前面的节点当第一组翻转后pre 需要指向新的头节点这个新头节点并没有一个“统一的处理入口”。有了 dummypre 一开始指向 dummy第一组翻转完成后让 dummy.next 指向新头后面所有组的操作都统一成“pre 指向当前组前驱 → 翻转当前组 → 更新 pre”。最后直接返回 dummy.next 即可不用管原 head 是哪个。这个模式在大量链表题里通用比如删除倒数第 N 个节点、两两交换节点都能套。3.2 外层循环的每一步细节迭代的整体逻辑可以拆成四步循环处理每一组第一步确认当前组的下边界。我们用 pre 作为组前驱它指向当前组的头节点的前一个节点。初始时 pre 是 dummy。每轮循环先把尾指针 tail 移动到 pre 的位置然后让它向后走 k 步。如果走到中途遇到 None说明剩余节点不足 k 个直接返回结果。第二步保存下一组的起点。tail 当前指向的是本组最后一个节点那下一组起点 nxt 就是 tail.next。这步必须在翻转之前完成。因为翻转后 tail.next 会被改写如果先翻转再取 nxt拿到的就是错的。第三步局部翻转。我们需要一个翻转区间 [head, nxt) 的辅助函数也就是从当前组头节点翻到下一组起点之前。翻完之后原来组头变成了组尾原来组尾变成了组头。第四步重接链表。把 pre.next 指向翻转后的新头再把翻转后的新尾就是原来的组头接上 nxt。最后把 pre 更新成翻转后的新尾开始下一轮循环。3.3 Python 完整实现先写辅助函数翻转左闭右开区间 [a, b)。注意 b 是边界不参与翻转。def reverse_left_right(a, b): prev None cur a while cur ! b: nxt cur.next cur.next prev prev cur cur nxt return prev主函数def reverse_k_group(head, k): dummy ListNode(-1) dummy.next head pre dummy while True: tail pre # 先看剩余节点够不够 k 个 for _ in range(k): tail tail.next if tail is None: return dummy.next # 保存下一组起点 nxt tail.next # 当前组的头节点 group_head pre.next # 翻转 [group_head, nxt) new_head reverse_left_right(group_head, nxt) # 重接链表 pre.next new_head group_head.next nxt # 更新 pre 为翻转后的组尾 pre group_head我在本地跑过的输出链表: 1 2 3 4 5, k2 - 2 1 4 3 5 链表: 1 2 3 4 5, k3 - 3 2 1 4 5 链表: 1 2 3 4 5, k1 - 1 2 3 4 53.4 两个常见失误tail 移动次数和 nxt 的保存时机第一个失误是 tail 的移动次数。注意 tail 初始指向 pre组前驱要让 tail 指向本组最后一个节点需要移动 k 次而不是 k-1 次。假设 pre 指向 dummy第一组头节点是节点 1k2 时第 1 次移动 tail 从 dummy 到节点 1第 2 次移动从节点 1 到节点 2。此时 tail 指向节点 2恰好是本组最后一个节点。如果你只移动 k-1 次tail 只能到节点 1翻转区间就会错。第二个失误是 nxt 一定得在翻转前保存。我在上面代码里把它放在翻转前这是有讲究的。翻转过程中 next 指针不断被重写等翻转完再找 tail.next那个值已经变成前一个节点了。你可以试想一下把 [1,2] 翻转成 [2,1] 后节点 2原来的尾的 next 指向节点 1而节点 1 的 next 指向 None原来的下一组入口节点 3 已经找不到了。所以“先保存、再处理”不是风格问题是正确性问题。4. 递归解法二把“每k组”翻译成子问题4.1 递归视角最大问题的最小切片递归解法的思想很优雅reverseKGroup(head, k) 这个函数本身就是解决“从 head 开始每 k 个一组翻转”。假设我们已经能处理 head 之后的剩余链表那当前的问题就变成翻转当前这 k 个节点再让这段的尾节点接上“剩余链表处理完后的头”。听着有点绕我们拆开看。先找到从 head 开始数的第 k 个节点它的 next 就是下一组的入口 nxt。对 nxt 调用 reverseKGroup(nxt, k)返回的就是“后半部分链表翻转完后的新头”。拿到这个新头之后再翻转当前这 k 个节点。翻转完成后当前组的原头 head 变成了尾节点让 head.next 指向后半部分的新头即可。最后返回当前组翻转后的新头。这个思路天然处理了“不足 k 个节点”的情况递归进入下一组前会先检查剩余长度如果不够 k 个直接原样返回上一组接回来的也就是未翻转的子链。4.2 Python 递归实现def reverse_k_group(head, k): # 先确认从 head 开始至少有 k 个节点 temp head for _ in range(k): if temp is None: return head temp temp.next # temp 现在指向第 k1 个节点也就是下一组入口 nxt temp # 递归处理后续部分 sub_head reverse_k_group(nxt, k) # 翻转当前组 [head, nxt) prev None cur head while cur ! nxt: node_next cur.next cur.next prev prev cur cur node_next # 翻转后 head 变成当前组尾节点接上后面处理完的链表 head.next sub_head # prev 是当前组翻转后的头节点 return prev核心逻辑和迭代版其实是同一个模型局部翻转 组间重接。只是迭代用 pre 指针从前往后推着走递归用调用栈从后往前逐层返回。4.3 递归边界为什么要先走 k 步很多同学看这段代码会疑惑为什么开头要专门用一个 temp 循环走 k 步而不是直接翻转原因是递归函数必须在“安全确认”之后再动手。翻一组节点没问题但如果剩余节点不足 k 个题目要求保持原顺序此时一翻就错了。所以每次进入递归的第一步是先“探路”探得够了才继续不够就返回原 head。探路的同时temp 停在的位置也正好是下一组入口这个信息后面的翻转循环和递归调用都要用。相当于一次遍历同时完成了长度校验和指针定位效率上不亏。4.4 递归写法容易绕晕的地方递归写法最绕的地方在 head.next sub_head 这一行。翻转循环结束后while 条件 cur ! nxt 保证 cur 正好停在 nxtprev 指向当前组的最后一个节点翻转后的头head 则成了当前组的最后一个节点翻转后的尾。如果你忘了让 head.next 指向 sub_head整条链表就会在这里断开后半部分彻底丢失。还有一点调用 sub_head reverse_k_group(nxt, k) 的时机在翻转当前组之前。这个顺序必须保证。因为翻转当前组会修改 head 到 nxt 之间所有节点的 next而 nxt 是需要传给递归的入口如果先翻转再递归nxt 节点本身的 next 也会被改递归就接到错误的位置上。先递归相当于先把后面的问题解决完再回头处理眼前这一段思路最清晰。5. 边界条件与调试经验6个决定成败的 Case5.1 六类边界输入的行为对照链表题一半的分数在边界处理上。下面这六类输入我建议你写完代码后逐个跑一遍输入特征期望行为为什么容易错head 为 None空链表返回 None循环判断 head 为空时容易空指针k 1链表完全不变每组一个节点翻转逻辑退化为无操作链表长度 k保持原样探路不足立即返回但返回的是原 head链表长度恰好是 k 的倍数所有组都翻转最后一组也参与翻转不能漏链表长度 k整条链表翻转和“单链表翻转”等价验证翻转函数本身链表长度 n*k 1最后一组单独剩余并保持原样不足 k 的节点只有 1 个容易误翻空链表的处理在两种解法里都靠循环天然兜底迭代版里 tail 从 pre 出发走 k 步第一步就会遇到 None 返回递归版里 temp 从 head 出发第一步就遇到 None 返回 head也就是 None。k1 的情况更微妙。迭代版里 tail 走 1 步到达组头翻转区间 [head, nxt) 只有一个节点翻转函数转一圈后返回原节点pre 更新为该节点继续下一轮。看起来没有报错但如果你的循环条件或者指针更新写错k1 时最容易出现死循环。我见过一个写法是在翻转后忘记更新 pre导致每一轮都处理同一个节点直接超时。5.2 三个典型错误写法与分析错误一没保存下一组入口就翻转。这类错误的现象是结果链表后半截丢失或者循环里出现环。根因就是我在 3.4 里说的“先保存、再处理”原则被违反。如果翻转后才取 tail.next拿到的已经是组内前一个节点链表就接不回去了。错误二用值交换冒充翻转。有些新手把每个节点的 val 收集到数组反转数组后再写回节点。这样确实能让输出看起来对但节点的 next 关系完全没有变化。面试官多问一句“如果节点是重度业务对象值交换可行吗”这个方案就站不住脚。链表题的考核点是结构操作不是数值搬运。错误三递归里把 sub_head 调用放在翻转之后。我之前强调过顺序问题。放在翻转之后递归入口 nxt 的 next 已经被改递归函数探路时从错误位置开始最终结果完全错乱。这类逻辑错误最坑的是小数据量测试可能恰好看不出来一旦 k 和链表长度凑出特定组合就是隐蔽 bug。5.3 我在调试时最常用的一招把链表转成数组打印链表题没有数组那么好打印所以调试起来特别费劲。我的做法是写一个统一的转存函数def list_to_array(head): result [] cur head seen set() # 防止链表成环导致死循环 while cur and id(cur) not in seen: seen.add(id(cur)) result.append(cur.val) cur cur.next return result每跑完一个用例直接 print(list_to_array(reverse_k_group(head, k)))一眼就能看出顺序对不对。seen 集合用来防环万一你的代码生成了循环链表这个函数会停止而不是让程序卡死。这个辅助函数我几乎每个链表题都用强烈建议你也准备一个。测试时把 5.1 的六类边界输入全部跑一遍尤其是“链表长度恰好是 k 的倍数”和“链表长度 n*k1”这两组它们能覆盖到绝大多数指针衔接错误。6. 复杂度、变体与这张题单的工程含义6.1 两种解法的时间和空间开销对比先看我实际测量的复杂度结论解法时间复杂度空间复杂度适用场景迭代 虚拟头节点O(n)O(1)日常实现首选无额外栈开销递归O(n)O(n/k)最坏 O(n)代码简洁但链表很长时栈风险高两种解法时间上都是 O(n)因为每个节点只会被访问常数次。迭代版额外维护了几个指针变量空间 O(1)。递归版每递归一层就会消耗一层调用栈层数是总节点数除以 k约为 n/k当 k1 时退化为 n栈深度可能爆掉。如果链表长度以万计面试时优先写迭代版。6.2 从这题出发的常见变形题“每 k 个一组翻转”是链表翻转家族里承上启下的一题。它会引出几个高频变形思路高度相关。第一个是两两交换链表中的节点本质就是 k2 的特殊情况可以用 reverseKGroup 的特化版也可以用递归一行版本。第二个是翻转链表的某一段比如给出 left 和 right只翻转区间 [left, right]。它和本题的局部翻转函数思路一致只是边界不同。第三个是“每 k 个一组翻转但最后不足 k 个也翻转”代码只需要把 5.1 里“不足保持原样”的兜底逻辑反过来探路不足时不是返回原 head而是继续翻转。第四个是链表整体翻转就是第 2 节里的三指针翻转它是所有变形的最小公因子。把这些问题放在一起看你会发现核心就两件事区间翻转函数怎么写以及区间外的链表如何连接。掌握好这两点这些变体几乎不用背。6.3 批翻转思想在工程里的影子从一个更宏观的视角看每 k 个一组翻转本质上是一个“分批处理”模型把一条长数据流切成固定大小的窗口每个窗口独立处理处理完再拼接回整体。这个模式在工程里到处都是。比如日志采集系统按批次聚合日志每 100 条做一次压缩后写入存储数据处理管线按照固定窗口大小做聚合计算播放器对视频帧做缓冲分组每组内部按时间戳排序后交给解码器数据库客户端批量提交事务时也是把大量操作切分成固定大小的批次。你甚至可以把链表想象成一条单向数据流分组、处理、重接这三个动作在任何批量作业调度器里都能找到对应物。所以这道题不只是面试题。理解“先保存上下文 → 处理当前批 → 重接上下文”的循环结构对理解真实系统里的批处理框架大有帮助。链表只是一个载体背后的思想才是它常年活跃在题单里的真正原因。我在实际刷题里的一个小经验是每写完一版链表题代码先自己设计一个五节点的链表把 k 分别设成 1、2、3、4、5 跑一遍再脑补一遍指针走向。这个过程大概五分钟但它能拦截掉绝大多数隐藏错误。链表题写到最后拼的就是细心和手感而这两种东西都是靠一次次画图、一个个边界 case 磨出来的。
阅读完成 · 觉得有帮助？
