LeetCode热题100里链表题不算多但K个一组翻转链表绝对属于那种“看题五分钟写码两小时”的经典。它不像206题反转链表那样三指针一背就完事也不像合并有序链表那样顺着直觉就能写对。它难在需要同时处理分组、反转、拼接三层动作稍有不慎链表要么断了要么成环要么后半截直接消失。我当年第一次做这题时自认为已经把反转链表背得滚瓜烂熟结果自己动手一写跑了三组测试用例一组死循环一组丢节点还有一组居然把下一组也翻进去了。今天这篇文章我围绕K个一组翻转链表完整拆一遍先讲清楚这题到底比普通反转难在哪再把边界条件一条条抠明白接着给出迭代和递归两种解法的逐步推导最后把我在本地调试时踩过的坑和测试方法全部摊开。无论你是刚开始刷题的新手还是准备面试想系统过链表题型的同学都可以直接按这个思路走。1. 从“反转链表”到“分组翻转”难度升级的那一步在哪题目本身不长我复述一下给你一个链表头节点head每K个节点一组进行翻转返回修改后的链表。K是一个正整数。如果节点总数不是K的整数倍最后剩余的节点保持原有顺序。而且题目明确要求不能只是改变节点内部的值要真正做节点交换。这最后一句话很关键它把投机取巧的路堵死了。有些人看到题先想着遍历一遍把值存数组里再倒着填回去这种方案在面试里直接就被否了。题目考察的是链表的指针操作不是数组搬运。那它比206题反转链表难在哪我总结下来是三件事叠加。第一分组。普通反转链表不需要判断“当前区间够不够长”从头翻到尾就结束。这道题每翻一组之前必须先验证从当前位置开始往后有没有K个节点。没有就保持原样返回有才允许动手。这个“先探测后操作”的步骤是很多人第一次写的时候最容易漏掉的。第二组内反转。虽然组内反转的基本手法和206题一样但它不是从链表头开始而是从任意一个节点的后继开始。你要小心处理这一组前面的那个节点也就是前驱。普通反转链表里prev最后会变成null这里prev必须指向上一组的尾部。第三组间拼接。每组翻转完成后这一组原本的头会变成尾原本的尾会变成头。你必须让“新头”接到上一组的尾部同时让“新尾”连上下一组的起点。如果这一组后面已经没有节点了那“新尾”就要指向null。这段拼接逻辑牵扯到四个关键位置前驱、组头、组尾、下一组起点。四个指针里只要有一个搞错链表结构就毁了。我用一个粗浅的类比反转链表是让你把一列车厢原地掉头K个一组翻转则是把整列火车按每K节拆开每段自己掉头再按顺序接回去。掉头这个动作你本来就会难的是“拆”和“接”的过程中不能碰坏其他车厢。也正因为如此这题在热题100里地位很高。它一次考查了迭代思想、边界思维和指针操作面试官还可以顺着它追问递归写法、空间复杂度优化甚至让你当场写一个变体。你要是能把这道题彻底吃透链表类的中等难度题目基本就稳了一半。2. 把边界条件当题目本身来读几种边界决定生死很多刷题攻略会说“链表题就是玩边界”这句话在K个一组翻转链表上体现得淋漓尽致。我先说结论这题的主干逻辑不复杂复杂的全是边界。先看最常见的边界链表长度不足K。题目语义是“最后剩余的节点保持原有顺序”也就是说如果链表一共5个节点而K3前三个翻转后面两个保持原样。实现时每轮开始前都要用一个探针节点从当前组前驱出发向后走K步走不完就说明后面不够一组了直接返回结果。再看K等于1。每1个节点一组翻转等于没翻。虽然代码里不需要专门特判也能跑对但如果你在校验阶段遇到极端测试用例K1会让循环次数变成0代码依然能正确返回原链表。有些同学会在开头写一个if k 1: return head的快速返回这其实是个好习惯既省时间也让后面的代码少了一层担忧。然后看K正好等于链表长度的情况。此时整条链表就是一组问题退化成“反转整条链表”。这个边界用来验证你的代码在“只有一组”的情况下能不能正确完成头尾翻转尤其是返回的头节点是否更新正确。还有一个容易被忽略的点链表本身为空或者只有一个节点。这两类情况在任何组数下都不会有实际翻转但代码必须能安全返回原链表。你不能在检查K个节点时直接对空指针做解引用。为什么说“把边界条件当题目本身来读”因为边界条件直接决定了代码的分支结构。我建议你在写代码之前先列一张测试用例表每一条都标清楚期望结果测试用例期望结果主要考察点空链表任意K返回空空指针安全单节点K1返回原链表最小规模单节点K1返回原链表不足K保持原序链表长度小于K完全不变提前退出链表长度等于K整条反转只有一组链表长度是K的倍数每K个一组完整翻转尾部拼接链表长度是K的倍数加1最后一组不动尾部滞留这张表不是面试官考你时才需要的是你自己在本地调试时就需要准备的东西。我每一次做链表题都会先跑这些用例跑通了再提交LeetCode基本上一次就能过。再解释一个几乎所有题解都会用、但很多人没想透的设计dummy哨兵节点。为什么非要它因为头节点可能参与翻转并且被移动到后面去。比如1-2-3K3翻转后头节点变成3如果你直接返回head那返回的就是原来的节点1已经变成尾部了整个链表等于丢了一半。dummy节点固定在链表头部之前不管你内部怎么翻最后返回dummy.next永远是当前链表的真实头节点。这是链表题里的通用套路这道题也只是其中之一。3. 迭代解法拆到骨头里头插法、区间反转法、完整代码迭代解法的实现方式很多我见过的主流写法至少有三种。这里我推荐两种最值得掌握的一种是“头插法”适合新手逻辑直观另一种是“区间反转法”更通用和92题反转链表II可以共用同一套思路。3.1 头插法为什么我推荐先用它上手头插法的核心思想并不复杂在一组节点内部不断地把“后面的节点”拽到“这一组的最前面”。重复K-1次整组就逆序了。我给你画一下过程。假设当前链表是1-2-3-4-5K3前面有一个dummy节点dummy.next指向1。此时我们定义两个角色pre当前组的前驱初始指向dummy。tail当前组的第一个节点初始指向pre.next也就是1。在头插过程中tail始终作为参照物存在它不会主动往后走但它后面永远挂着没处理完的节点。开始循环一共执行K-1次也就是2次。第一次取出tail.next也就是节点2。让tail.next先指向节点2的后继也就是节点3相当于把节点2从链表中“摘”出来。然后让节点2的next指向pre.next也就是节点1。最后让pre.next指向节点2。此时链表变成dummy-2-1-3-4-5。注意看2被插到了最前面1自然往后退了一位。第二次继续取出tail.next此时tail还是节点1tail.next指向的是3。照葫芦画瓢tail.next指向43的next指向pre.next也就是当前最前面的2pre.next指向3。链表变成dummy-3-2-1-4-5。到这里本组3个节点翻转完成结果为3-2-1。接下来要做的是让pre移动到本组末尾也就是tail指向的节点1tail再更新为pre.next也就是节点4开始下一组。整个过程中你需要关注的角色是pre、tail、nextGroup这四个位置。nextGroup是本组最后一个节点的next在开始翻转前就要提前保存好否则反转过程中会丢。头插法最大的好处是它不太需要你同时倒腾prev、cur、next三个指针只要记住“每次都把tail.next摘到pre后面”这一个动作循环K-1次即可。对新手来说这是最容易安睡的写法。3.2 头插法完整代码与逐行注释我直接给Python版本的完整实现每段关键代码后面写清楚它在干什么。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def reverseKGroup(head: ListNode, k: int) - ListNode: dummy ListNode(0) dummy.next head pre dummy while pre: # 1. 从pre出发检查后面还有没有k个节点 end pre for _ in range(k): end end.next if not end: return dummy.next # 2. 记录下一组起点 next_group end.next # 3. 头插法翻转本组 tail pre.next # tail始终指向本组第一个节点 for _ in range(k - 1): cur tail.next # 要摘下来的节点 tail.next cur.next # 先把tail.next跳到更后面的节点 cur.next pre.next # 把摘下来的节点放到pre后面 pre.next cur # 更新pre.next # 4. 把翻转后的本组尾部tail接到下一组起点 tail.next next_group # 5. 移动pre到本组末尾准备下一轮 pre tail return dummy.next这里有几个细节你一定要注意。检查K个节点用的是end从pre出发而不是从pre.next出发。因为pre指向的是上一组的尾部下一组从pre.next开始。如果你不小心让end从pre开始走K步那实际检查到的组会往后多偏一个节点第一组的头就会漏掉。头插法循环次数是K-1。为什么要减1因为每组有K个节点第一个节点tail本身已经在最前面了只需要把后面K-1个节点挨个插到它的前面整体就逆序了。如果你写成K次会把下一组的第一个节点也拽进来链表彻底错乱。翻转完成后tail指向的不再是组头而是组尾。这个很反直觉因为tail从头到尾都没动过只是它后面挂的节点不断被摘走又插到前面等循环结束时它已经被挤到了最后。所以最后要执行tail.next next_group来把本组尾部接到后续链表上。3.3 区间反转法另一种实现与对比头插法虽好但有些面试官更希望你展示通用的区间反转能力。这时可以用三指针法思路和反转链表II完全一致。核心逻辑是在区间[start, end]内部用prev、cur、next三个指针逐节点反转。先找到起点前驱pre再通过K步移动找到区间终点end随即设置next_group end.next然后从pre.next开始一路反转到next_group为止。def reverseKGroup(head: ListNode, k: int) - ListNode: dummy ListNode(0) dummy.next head pre dummy while True: # 检查是否够k个 end pre for _ in range(k): end end.next if end is None: return dummy.next next_group end.next # 区间反转 [pre.next, end] prev pre cur pre.next while cur ! next_group: temp cur.next cur.next prev prev cur cur temp # 翻转后pre.next还指向旧头需要把它改成新头 tail pre.next # 旧头翻转后变成新尾 pre.next prev # prev指向end也就是新头 tail.next next_group pre tail区间反转法的拼接逻辑比头插法稍微绕一点翻转完成后你的pre变量还是原来的前驱pre.next还是旧头但旧头此刻已经是新尾了。这时候你必须先保存tail pre.next然后把pre.next指向新头prev最后再把tail.next指向next_group。三步顺序不能乱。这两份代码的时间复杂度都是O(n)空间复杂度O(1)。面试时先说头插法再说“我还可以用区间反转法做92题那条思路直接套”这是很完整的展示。4. 递归解法每一次调用只负责一组节点的翻转迭代解法能解决90%的场景但递归解法值得单独练一遍因为它能帮你把思路更清晰地表达出来每一层递归只处理一组剩下的交给下一层。4.1 递归的核心思路你把reverseKGroup(head, k)理解为翻转“以head开头从当前位置起每K个一组”的链表并返回新的头节点。递归的逻辑是这样展开的。先检查从head开始往后有没有K个节点用一个探针指针往后走K步。如果走不完说明不足一组直接返回head保持原序。如果走完了探针就停在了“本组最后一个节点”的位置。注意这里有一个很聪明的选择我不把探针停在最后一个节点而是让它停在最后一个节点的后继上也就是下一组的起点。这样我们翻转的区间就是一个半开区间[head, end)end指向的是下一组第一个节点。为什么用半开区间因为在写递归拼接时会非常省事。翻转半开区间[head, end)以后end仍然是指向下一组起点的那个节点你直接把它传给递归调用就行不需要额外保存next_group。4.2 半开区间的妙处我们来看半开区间翻转的具体写法。目标是把head到end前一个节点这K个节点逆序然后返回逆序后的新头。def reverse_range(head: ListNode, end: ListNode) - ListNode: prev None cur head while cur ! end: temp cur.next cur.next prev prev cur cur temp return prev这段代码是不是很眼熟它就是206题反转链表的写法只不过终止条件从cur is None换成了cur ! end。当cur走到end时循环停止此时prev正好指向原区间的最后一个节点也就是翻转后的新头。这里终点end不参与翻转这就是半开区间的含义。为什么要让end不参与就是因为end本身被外界当成“边界”使用它既作为本组翻转的终点又作为下一组处理的起点。这个设计让代码少了一整段“找边界、存边界、接边界”的麻烦。4.3 递归完整代码与复杂度有了reverse_range主体代码可以写得非常干净。def reverseKGroup(head: ListNode, k: int) - ListNode: if not head: return None end head for _ in range(k): if not end: return head # 不足k个保持原序 end end.next new_head reverse_range(head, end) # 翻转本组 [head, end) head.next reverseKGroup(end, k) # 递归处理下一组并接上 return new_head每次递归的流程只有三句话判断一组是否完整、翻转当前组、让当前组末尾指向下一组的结果。空间复杂度方面递归会消耗栈空间栈的深度等于组数也就是O(n/k)。虽然这不算很大的开销但面试官如果追问“能不能把空间复杂度降到O(1)”你只需要回答“可以把递归改成迭代用dummy哨兵维护前驱即可”。这一问一答之间两种解法的优劣就都说清楚了。我个人建议如果你有足够时间两种写法都练熟。迭代版用来快速提交和面试主答递归版用来展示思路、在代码量少的场景下快速表达。两种都会了这道题才算真正消化成自己的东西。5. 从25题往外看几个高频变体与连带考点一道好题值得反复变着花样用。K个一组翻转链表衍生出来的变体在面试里非常常见这里我挑三个最典型的展开。5.1 变体一不足K个也要翻转这个变体要求最后剩余的节点也参与翻转整个链表按照每K个一组全部逆序不允许末尾保留原序。最简单可靠的改法先遍历一遍链表统计总长度算出完整的组数N。然后只对前K*N个节点执行标准翻转剩余长度小于K的节点在最后一轮一并当作一组翻转即可。本质上你只是把“检查不足K保持原序”的终止条件改成了“已经处理完所有完整组后把剩余部分也翻一次”。也有另一种实现先整体判断余数然后修改外层循环的退出条件让最后一组不足K时也强制进入反转流程。但这个写法容易和“保持原序”的分支混在一起代码可读性差我一般不推荐。5.2 变体二两两交换链表中的节点就是K2LeetCode第24题“两两交换链表中的节点”本质上就是这道题在K2时的特例。你把K设置成2头插法的循环只需要执行1次代码跑起来的结果正好就是相邻节点两两交换。有意思的是如果你掌握了递归版reverseKGroup第24题甚至不需要单独准备直接把K2传进去就行。面试时如果先做到第24题再让面试官出“改成每K个一组”的升级题你就能顺着同一份代码自然过渡显得基本功特别扎实。5.3 变体三从链表尾部开始每K个一组翻转这个变体乍一看很抽象它会说“从尾部开始分组翻转”比如1-2-3-4-5K2前两个节点可能保持不动后面的4和5翻转、2和3翻转。常规解法的思路特别巧妙先对整个链表做一次完整反转于是尾部变成了头部。然后在这个“已经反转的链表”上执行标准的K个一组翻转最后再把整个链表反转回来。三次反转换来一次分组翻转逻辑完全复用代码量很少。这个技巧的本质是把“依赖尾部”的问题转化为“依赖头部”的问题再进行标准处理。我面试时很喜欢这个题因为它考察的不是背模板而是对反转操作本身的理解。5.4 和92题反转链表II的连带关系92题要求反转区间[left, right]之间的节点是典型的单区间反转。K个一组翻转链表则是反复进行等长区间反转。如果你已经会25题再看92题会发现它只是“跳过了前驱、只反转一次”的简化版。这就引出一条很重要的学习路径先学206题掌握基础三指针反转再学92题掌握任意区间反转最后学25题掌握连续区间反转边界判断。三步走完链表题里最核心的指针操作工具包基本就成型了。6. 实测调试心得我在本地环境踩过的坑和验证方法刷题最难受的不是不会写而是写完了不知道错在哪。K个一组翻转链表尤其如此因为链表结构一旦断裂print调试都不太容易定位。这里我把自己的调试流程和踩坑记录分享出来。6.1 我在本地踩过的高频坑第一个坑检查完K个节点后忘记把tail.next接到next_group。在头插法版本里一共K-1次头插完成后tail已经变成原组的最后一个节点。如果你忘了让它指向next_group整条链表从本组尾部往后就全丢了。这种问题最阴险因为它不是崩溃也不是报错而是链表悄悄变短你只会在结果上看到少了几个节点。第二个坑头插循环次数写成K而不是K-1。我最早写头插法时心想“有几个节点就摘几次”结果把下一组的第一个节点也作为当前组的一部分翻进来了。表现是前一组翻转后会多“吞”一个节点后续分组全部错位。第三个坑在迭代版本里检查K个节点时把探针初始化为pre.next而不是pre。从pre.next开始走K步实际会把本组第一个节点排除在外。比如K3时走完3步停在了第三个节点后面检查组只有两个节点。这种错误比较隐蔽尤其在你只是改了一行代码时更容易犯。第四个坑交换完dummy的拼接顺序。区间反转法里保存旧头的操作如果放在pre.next prev之后再做你保存到的就已经是新头了链表拼接直接错乱。记住原则先保存旧头再改pre.next最后用旧头连后续。6.2 打印调试法每轮都看两眼链表如果你在本地调试不要只靠眼睛在纸上推演写一个简单的打印函数会省下大量时间。def print_list(head: ListNode): vals [] while head: vals.append(str(head.val)) head head.next print( - .join(vals))在头插法版本里我建议在两处调用这个函数一处是每轮开始前打印当前链表状态另一处是本组翻转结束后、pre移动前打印拼接完的结果。两次对照你立刻能看出这一组有没有翻对、尾部有没有接上。实践下来大多数问题都在“翻转结束后”这个打印点现出原形。6.3 本地测试用例与断言我在本地建了一个简单的测试脚本专门用来跑边界用例。def build_list(arr): dummy ListNode(0) cur dummy for v in arr: cur.next ListNode(v) cur cur.next return dummy.next def to_list(head): res [] while head: res.append(head.val) head head.next return res assert to_list(reverseKGroup(build_list([1,2,3,4,5]), 3)) [3,2,1,4,5] assert to_list(reverseKGroup(build_list([1,2,3,4,5]), 1)) [1,2,3,4,5] assert to_list(reverseKGroup(build_list([1,2,3,4,5]), 2)) [2,1,4,3,5] assert to_list(reverseKGroup(build_list([1,2,3,4]), 2)) [2,1,4,3] assert to_list(reverseKGroup(build_list([1,2]), 3)) [1,2] assert to_list(reverseKGroup(build_list([]), 3)) [] assert to_list(reverseKGroup(build_list([1]), 1)) [1]这套断言基本覆盖了我上表格列出的边界。每次改完代码跑一遍所有断言能过就说明核心逻辑没问题再丢到LeetCode上做最终验证。因为LeetCode的判题环境自带随机测试用例但我发现很多边界情况它未必每次都覆盖本地多跑一分面试就少一分风险。6.4 面试时的节奏建议最后聊聊面试现场怎么答这题。别上来就埋头写代码先说清楚题目语义尤其要和面试官确认“不足K个保持原序”这一点这既避免理解偏差也展示了你的沟通习惯。然后简单说思路用dummy哨兵每轮检查K个节点组内用三指针或头插法翻转组间做拼接。说完复杂度O(n)时间、O(1)空间再动手。如果面试官要求优化或变体就顺着上一章说的几个变体展开。你不需要把所有变体都写一遍能说出思路并写一个变体就够了。这题真正想考验的是你在链表指针操作中能不能保持冷静、有条理而这恰恰是可以靠提前练习做到的。
K个一组翻转链表：迭代与递归双解法及边界条件剖析
LeetCode热题100里链表题不算多但K个一组翻转链表绝对属于那种“看题五分钟写码两小时”的经典。它不像206题反转链表那样三指针一背就完事也不像合并有序链表那样顺着直觉就能写对。它难在需要同时处理分组、反转、拼接三层动作稍有不慎链表要么断了要么成环要么后半截直接消失。我当年第一次做这题时自认为已经把反转链表背得滚瓜烂熟结果自己动手一写跑了三组测试用例一组死循环一组丢节点还有一组居然把下一组也翻进去了。今天这篇文章我围绕K个一组翻转链表完整拆一遍先讲清楚这题到底比普通反转难在哪再把边界条件一条条抠明白接着给出迭代和递归两种解法的逐步推导最后把我在本地调试时踩过的坑和测试方法全部摊开。无论你是刚开始刷题的新手还是准备面试想系统过链表题型的同学都可以直接按这个思路走。1. 从“反转链表”到“分组翻转”难度升级的那一步在哪题目本身不长我复述一下给你一个链表头节点head每K个节点一组进行翻转返回修改后的链表。K是一个正整数。如果节点总数不是K的整数倍最后剩余的节点保持原有顺序。而且题目明确要求不能只是改变节点内部的值要真正做节点交换。这最后一句话很关键它把投机取巧的路堵死了。有些人看到题先想着遍历一遍把值存数组里再倒着填回去这种方案在面试里直接就被否了。题目考察的是链表的指针操作不是数组搬运。那它比206题反转链表难在哪我总结下来是三件事叠加。第一分组。普通反转链表不需要判断“当前区间够不够长”从头翻到尾就结束。这道题每翻一组之前必须先验证从当前位置开始往后有没有K个节点。没有就保持原样返回有才允许动手。这个“先探测后操作”的步骤是很多人第一次写的时候最容易漏掉的。第二组内反转。虽然组内反转的基本手法和206题一样但它不是从链表头开始而是从任意一个节点的后继开始。你要小心处理这一组前面的那个节点也就是前驱。普通反转链表里prev最后会变成null这里prev必须指向上一组的尾部。第三组间拼接。每组翻转完成后这一组原本的头会变成尾原本的尾会变成头。你必须让“新头”接到上一组的尾部同时让“新尾”连上下一组的起点。如果这一组后面已经没有节点了那“新尾”就要指向null。这段拼接逻辑牵扯到四个关键位置前驱、组头、组尾、下一组起点。四个指针里只要有一个搞错链表结构就毁了。我用一个粗浅的类比反转链表是让你把一列车厢原地掉头K个一组翻转则是把整列火车按每K节拆开每段自己掉头再按顺序接回去。掉头这个动作你本来就会难的是“拆”和“接”的过程中不能碰坏其他车厢。也正因为如此这题在热题100里地位很高。它一次考查了迭代思想、边界思维和指针操作面试官还可以顺着它追问递归写法、空间复杂度优化甚至让你当场写一个变体。你要是能把这道题彻底吃透链表类的中等难度题目基本就稳了一半。2. 把边界条件当题目本身来读几种边界决定生死很多刷题攻略会说“链表题就是玩边界”这句话在K个一组翻转链表上体现得淋漓尽致。我先说结论这题的主干逻辑不复杂复杂的全是边界。先看最常见的边界链表长度不足K。题目语义是“最后剩余的节点保持原有顺序”也就是说如果链表一共5个节点而K3前三个翻转后面两个保持原样。实现时每轮开始前都要用一个探针节点从当前组前驱出发向后走K步走不完就说明后面不够一组了直接返回结果。再看K等于1。每1个节点一组翻转等于没翻。虽然代码里不需要专门特判也能跑对但如果你在校验阶段遇到极端测试用例K1会让循环次数变成0代码依然能正确返回原链表。有些同学会在开头写一个if k 1: return head的快速返回这其实是个好习惯既省时间也让后面的代码少了一层担忧。然后看K正好等于链表长度的情况。此时整条链表就是一组问题退化成“反转整条链表”。这个边界用来验证你的代码在“只有一组”的情况下能不能正确完成头尾翻转尤其是返回的头节点是否更新正确。还有一个容易被忽略的点链表本身为空或者只有一个节点。这两类情况在任何组数下都不会有实际翻转但代码必须能安全返回原链表。你不能在检查K个节点时直接对空指针做解引用。为什么说“把边界条件当题目本身来读”因为边界条件直接决定了代码的分支结构。我建议你在写代码之前先列一张测试用例表每一条都标清楚期望结果测试用例期望结果主要考察点空链表任意K返回空空指针安全单节点K1返回原链表最小规模单节点K1返回原链表不足K保持原序链表长度小于K完全不变提前退出链表长度等于K整条反转只有一组链表长度是K的倍数每K个一组完整翻转尾部拼接链表长度是K的倍数加1最后一组不动尾部滞留这张表不是面试官考你时才需要的是你自己在本地调试时就需要准备的东西。我每一次做链表题都会先跑这些用例跑通了再提交LeetCode基本上一次就能过。再解释一个几乎所有题解都会用、但很多人没想透的设计dummy哨兵节点。为什么非要它因为头节点可能参与翻转并且被移动到后面去。比如1-2-3K3翻转后头节点变成3如果你直接返回head那返回的就是原来的节点1已经变成尾部了整个链表等于丢了一半。dummy节点固定在链表头部之前不管你内部怎么翻最后返回dummy.next永远是当前链表的真实头节点。这是链表题里的通用套路这道题也只是其中之一。3. 迭代解法拆到骨头里头插法、区间反转法、完整代码迭代解法的实现方式很多我见过的主流写法至少有三种。这里我推荐两种最值得掌握的一种是“头插法”适合新手逻辑直观另一种是“区间反转法”更通用和92题反转链表II可以共用同一套思路。3.1 头插法为什么我推荐先用它上手头插法的核心思想并不复杂在一组节点内部不断地把“后面的节点”拽到“这一组的最前面”。重复K-1次整组就逆序了。我给你画一下过程。假设当前链表是1-2-3-4-5K3前面有一个dummy节点dummy.next指向1。此时我们定义两个角色pre当前组的前驱初始指向dummy。tail当前组的第一个节点初始指向pre.next也就是1。在头插过程中tail始终作为参照物存在它不会主动往后走但它后面永远挂着没处理完的节点。开始循环一共执行K-1次也就是2次。第一次取出tail.next也就是节点2。让tail.next先指向节点2的后继也就是节点3相当于把节点2从链表中“摘”出来。然后让节点2的next指向pre.next也就是节点1。最后让pre.next指向节点2。此时链表变成dummy-2-1-3-4-5。注意看2被插到了最前面1自然往后退了一位。第二次继续取出tail.next此时tail还是节点1tail.next指向的是3。照葫芦画瓢tail.next指向43的next指向pre.next也就是当前最前面的2pre.next指向3。链表变成dummy-3-2-1-4-5。到这里本组3个节点翻转完成结果为3-2-1。接下来要做的是让pre移动到本组末尾也就是tail指向的节点1tail再更新为pre.next也就是节点4开始下一组。整个过程中你需要关注的角色是pre、tail、nextGroup这四个位置。nextGroup是本组最后一个节点的next在开始翻转前就要提前保存好否则反转过程中会丢。头插法最大的好处是它不太需要你同时倒腾prev、cur、next三个指针只要记住“每次都把tail.next摘到pre后面”这一个动作循环K-1次即可。对新手来说这是最容易安睡的写法。3.2 头插法完整代码与逐行注释我直接给Python版本的完整实现每段关键代码后面写清楚它在干什么。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def reverseKGroup(head: ListNode, k: int) - ListNode: dummy ListNode(0) dummy.next head pre dummy while pre: # 1. 从pre出发检查后面还有没有k个节点 end pre for _ in range(k): end end.next if not end: return dummy.next # 2. 记录下一组起点 next_group end.next # 3. 头插法翻转本组 tail pre.next # tail始终指向本组第一个节点 for _ in range(k - 1): cur tail.next # 要摘下来的节点 tail.next cur.next # 先把tail.next跳到更后面的节点 cur.next pre.next # 把摘下来的节点放到pre后面 pre.next cur # 更新pre.next # 4. 把翻转后的本组尾部tail接到下一组起点 tail.next next_group # 5. 移动pre到本组末尾准备下一轮 pre tail return dummy.next这里有几个细节你一定要注意。检查K个节点用的是end从pre出发而不是从pre.next出发。因为pre指向的是上一组的尾部下一组从pre.next开始。如果你不小心让end从pre开始走K步那实际检查到的组会往后多偏一个节点第一组的头就会漏掉。头插法循环次数是K-1。为什么要减1因为每组有K个节点第一个节点tail本身已经在最前面了只需要把后面K-1个节点挨个插到它的前面整体就逆序了。如果你写成K次会把下一组的第一个节点也拽进来链表彻底错乱。翻转完成后tail指向的不再是组头而是组尾。这个很反直觉因为tail从头到尾都没动过只是它后面挂的节点不断被摘走又插到前面等循环结束时它已经被挤到了最后。所以最后要执行tail.next next_group来把本组尾部接到后续链表上。3.3 区间反转法另一种实现与对比头插法虽好但有些面试官更希望你展示通用的区间反转能力。这时可以用三指针法思路和反转链表II完全一致。核心逻辑是在区间[start, end]内部用prev、cur、next三个指针逐节点反转。先找到起点前驱pre再通过K步移动找到区间终点end随即设置next_group end.next然后从pre.next开始一路反转到next_group为止。def reverseKGroup(head: ListNode, k: int) - ListNode: dummy ListNode(0) dummy.next head pre dummy while True: # 检查是否够k个 end pre for _ in range(k): end end.next if end is None: return dummy.next next_group end.next # 区间反转 [pre.next, end] prev pre cur pre.next while cur ! next_group: temp cur.next cur.next prev prev cur cur temp # 翻转后pre.next还指向旧头需要把它改成新头 tail pre.next # 旧头翻转后变成新尾 pre.next prev # prev指向end也就是新头 tail.next next_group pre tail区间反转法的拼接逻辑比头插法稍微绕一点翻转完成后你的pre变量还是原来的前驱pre.next还是旧头但旧头此刻已经是新尾了。这时候你必须先保存tail pre.next然后把pre.next指向新头prev最后再把tail.next指向next_group。三步顺序不能乱。这两份代码的时间复杂度都是O(n)空间复杂度O(1)。面试时先说头插法再说“我还可以用区间反转法做92题那条思路直接套”这是很完整的展示。4. 递归解法每一次调用只负责一组节点的翻转迭代解法能解决90%的场景但递归解法值得单独练一遍因为它能帮你把思路更清晰地表达出来每一层递归只处理一组剩下的交给下一层。4.1 递归的核心思路你把reverseKGroup(head, k)理解为翻转“以head开头从当前位置起每K个一组”的链表并返回新的头节点。递归的逻辑是这样展开的。先检查从head开始往后有没有K个节点用一个探针指针往后走K步。如果走不完说明不足一组直接返回head保持原序。如果走完了探针就停在了“本组最后一个节点”的位置。注意这里有一个很聪明的选择我不把探针停在最后一个节点而是让它停在最后一个节点的后继上也就是下一组的起点。这样我们翻转的区间就是一个半开区间[head, end)end指向的是下一组第一个节点。为什么用半开区间因为在写递归拼接时会非常省事。翻转半开区间[head, end)以后end仍然是指向下一组起点的那个节点你直接把它传给递归调用就行不需要额外保存next_group。4.2 半开区间的妙处我们来看半开区间翻转的具体写法。目标是把head到end前一个节点这K个节点逆序然后返回逆序后的新头。def reverse_range(head: ListNode, end: ListNode) - ListNode: prev None cur head while cur ! end: temp cur.next cur.next prev prev cur cur temp return prev这段代码是不是很眼熟它就是206题反转链表的写法只不过终止条件从cur is None换成了cur ! end。当cur走到end时循环停止此时prev正好指向原区间的最后一个节点也就是翻转后的新头。这里终点end不参与翻转这就是半开区间的含义。为什么要让end不参与就是因为end本身被外界当成“边界”使用它既作为本组翻转的终点又作为下一组处理的起点。这个设计让代码少了一整段“找边界、存边界、接边界”的麻烦。4.3 递归完整代码与复杂度有了reverse_range主体代码可以写得非常干净。def reverseKGroup(head: ListNode, k: int) - ListNode: if not head: return None end head for _ in range(k): if not end: return head # 不足k个保持原序 end end.next new_head reverse_range(head, end) # 翻转本组 [head, end) head.next reverseKGroup(end, k) # 递归处理下一组并接上 return new_head每次递归的流程只有三句话判断一组是否完整、翻转当前组、让当前组末尾指向下一组的结果。空间复杂度方面递归会消耗栈空间栈的深度等于组数也就是O(n/k)。虽然这不算很大的开销但面试官如果追问“能不能把空间复杂度降到O(1)”你只需要回答“可以把递归改成迭代用dummy哨兵维护前驱即可”。这一问一答之间两种解法的优劣就都说清楚了。我个人建议如果你有足够时间两种写法都练熟。迭代版用来快速提交和面试主答递归版用来展示思路、在代码量少的场景下快速表达。两种都会了这道题才算真正消化成自己的东西。5. 从25题往外看几个高频变体与连带考点一道好题值得反复变着花样用。K个一组翻转链表衍生出来的变体在面试里非常常见这里我挑三个最典型的展开。5.1 变体一不足K个也要翻转这个变体要求最后剩余的节点也参与翻转整个链表按照每K个一组全部逆序不允许末尾保留原序。最简单可靠的改法先遍历一遍链表统计总长度算出完整的组数N。然后只对前K*N个节点执行标准翻转剩余长度小于K的节点在最后一轮一并当作一组翻转即可。本质上你只是把“检查不足K保持原序”的终止条件改成了“已经处理完所有完整组后把剩余部分也翻一次”。也有另一种实现先整体判断余数然后修改外层循环的退出条件让最后一组不足K时也强制进入反转流程。但这个写法容易和“保持原序”的分支混在一起代码可读性差我一般不推荐。5.2 变体二两两交换链表中的节点就是K2LeetCode第24题“两两交换链表中的节点”本质上就是这道题在K2时的特例。你把K设置成2头插法的循环只需要执行1次代码跑起来的结果正好就是相邻节点两两交换。有意思的是如果你掌握了递归版reverseKGroup第24题甚至不需要单独准备直接把K2传进去就行。面试时如果先做到第24题再让面试官出“改成每K个一组”的升级题你就能顺着同一份代码自然过渡显得基本功特别扎实。5.3 变体三从链表尾部开始每K个一组翻转这个变体乍一看很抽象它会说“从尾部开始分组翻转”比如1-2-3-4-5K2前两个节点可能保持不动后面的4和5翻转、2和3翻转。常规解法的思路特别巧妙先对整个链表做一次完整反转于是尾部变成了头部。然后在这个“已经反转的链表”上执行标准的K个一组翻转最后再把整个链表反转回来。三次反转换来一次分组翻转逻辑完全复用代码量很少。这个技巧的本质是把“依赖尾部”的问题转化为“依赖头部”的问题再进行标准处理。我面试时很喜欢这个题因为它考察的不是背模板而是对反转操作本身的理解。5.4 和92题反转链表II的连带关系92题要求反转区间[left, right]之间的节点是典型的单区间反转。K个一组翻转链表则是反复进行等长区间反转。如果你已经会25题再看92题会发现它只是“跳过了前驱、只反转一次”的简化版。这就引出一条很重要的学习路径先学206题掌握基础三指针反转再学92题掌握任意区间反转最后学25题掌握连续区间反转边界判断。三步走完链表题里最核心的指针操作工具包基本就成型了。6. 实测调试心得我在本地环境踩过的坑和验证方法刷题最难受的不是不会写而是写完了不知道错在哪。K个一组翻转链表尤其如此因为链表结构一旦断裂print调试都不太容易定位。这里我把自己的调试流程和踩坑记录分享出来。6.1 我在本地踩过的高频坑第一个坑检查完K个节点后忘记把tail.next接到next_group。在头插法版本里一共K-1次头插完成后tail已经变成原组的最后一个节点。如果你忘了让它指向next_group整条链表从本组尾部往后就全丢了。这种问题最阴险因为它不是崩溃也不是报错而是链表悄悄变短你只会在结果上看到少了几个节点。第二个坑头插循环次数写成K而不是K-1。我最早写头插法时心想“有几个节点就摘几次”结果把下一组的第一个节点也作为当前组的一部分翻进来了。表现是前一组翻转后会多“吞”一个节点后续分组全部错位。第三个坑在迭代版本里检查K个节点时把探针初始化为pre.next而不是pre。从pre.next开始走K步实际会把本组第一个节点排除在外。比如K3时走完3步停在了第三个节点后面检查组只有两个节点。这种错误比较隐蔽尤其在你只是改了一行代码时更容易犯。第四个坑交换完dummy的拼接顺序。区间反转法里保存旧头的操作如果放在pre.next prev之后再做你保存到的就已经是新头了链表拼接直接错乱。记住原则先保存旧头再改pre.next最后用旧头连后续。6.2 打印调试法每轮都看两眼链表如果你在本地调试不要只靠眼睛在纸上推演写一个简单的打印函数会省下大量时间。def print_list(head: ListNode): vals [] while head: vals.append(str(head.val)) head head.next print( - .join(vals))在头插法版本里我建议在两处调用这个函数一处是每轮开始前打印当前链表状态另一处是本组翻转结束后、pre移动前打印拼接完的结果。两次对照你立刻能看出这一组有没有翻对、尾部有没有接上。实践下来大多数问题都在“翻转结束后”这个打印点现出原形。6.3 本地测试用例与断言我在本地建了一个简单的测试脚本专门用来跑边界用例。def build_list(arr): dummy ListNode(0) cur dummy for v in arr: cur.next ListNode(v) cur cur.next return dummy.next def to_list(head): res [] while head: res.append(head.val) head head.next return res assert to_list(reverseKGroup(build_list([1,2,3,4,5]), 3)) [3,2,1,4,5] assert to_list(reverseKGroup(build_list([1,2,3,4,5]), 1)) [1,2,3,4,5] assert to_list(reverseKGroup(build_list([1,2,3,4,5]), 2)) [2,1,4,3,5] assert to_list(reverseKGroup(build_list([1,2,3,4]), 2)) [2,1,4,3] assert to_list(reverseKGroup(build_list([1,2]), 3)) [1,2] assert to_list(reverseKGroup(build_list([]), 3)) [] assert to_list(reverseKGroup(build_list([1]), 1)) [1]这套断言基本覆盖了我上表格列出的边界。每次改完代码跑一遍所有断言能过就说明核心逻辑没问题再丢到LeetCode上做最终验证。因为LeetCode的判题环境自带随机测试用例但我发现很多边界情况它未必每次都覆盖本地多跑一分面试就少一分风险。6.4 面试时的节奏建议最后聊聊面试现场怎么答这题。别上来就埋头写代码先说清楚题目语义尤其要和面试官确认“不足K个保持原序”这一点这既避免理解偏差也展示了你的沟通习惯。然后简单说思路用dummy哨兵每轮检查K个节点组内用三指针或头插法翻转组间做拼接。说完复杂度O(n)时间、O(1)空间再动手。如果面试官要求优化或变体就顺着上一章说的几个变体展开。你不需要把所有变体都写一遍能说出思路并写一个变体就够了。这题真正想考验的是你在链表指针操作中能不能保持冷静、有条理而这恰恰是可以靠提前练习做到的。
