链表题在算法面试里出现频率极高而k个一组反转又是其中最能拉开差距的一类。它不像整体反转那样一趟走完就结束也不像两两交换那样规则固定它要求你在递归与迭代之间做出选择还要处理最后不足k个节点时的边界情况。很多人第一次写这道题代码在纸上推演没问题一跑就报空指针或者反转完发现链表断了、顺序乱了。这篇内容就把这道题从头到尾拆开讲清楚每一步为什么这么写以及我在实际练习中踩过的那些坑。1. 先搞清楚这道题到底在考什么1.1 题目本身的约束条件这道题的标准描述是给你一个链表的头节点每k个节点为一组进行反转返回修改后的链表。如果最后剩余的节点数量不足k个则保持它们原有的顺序。看起来简单但魔鬼藏在细节里。k1的时候什么都不用做k等于链表长度的时候等价于整体反转k大于链表长度的时候直接返回原链表。这三种边界情况如果不在脑子里过一遍写出来的代码大概率会在某个测试用例上挂掉。我个人的习惯是拿到任何链表题先在纸上画一个长度为6的链表然后分别用k2、k3、k4手动推演一遍。这个过程看起来笨但它能帮你在写代码之前就把指针的走向想清楚比上来就敲键盘效率高得多。1.2 为什么这道题比整体反转难整体反转链表只需要维护三个指针前驱、当前、后继一路走到底就行。但k个一组反转引入了分组的概念你需要在反转每一组之前先确认这一组是否有k个节点反转之后还要把上一组的尾节点和这一组的头节点接上同时把这一组的尾节点和下一组的头节点接上。换句话说整体反转只关心一条链而k个一组反转关心的是链与链之间的拼接关系。这就是为什么很多人单独写反转函数没问题但一拼接就出错。1.3 两种主流解法的取舍递归和迭代都能解这道题。递归的代码更简洁思路是反转前k个然后递归处理剩下的把两段接起来。迭代的代码稍长但不需要额外的栈空间在大规模数据下更稳妥。我在练习阶段建议两种都写一遍。递归帮你理解问题的分解方式迭代帮你掌握指针操作的精确性。面试的时候如果面试官没有特别要求选你写得最稳的那种就行。但如果你能主动说出两种解法的取舍那绝对是加分项。2. 递归解法的完整推导过程2.1 递归的核心思路拆解递归解法的本质是把一个大问题拆成两个子问题第一个子问题是反转当前这k个节点第二个子问题是处理剩余的链表。关键在于反转完当前这k个节点之后原来的头节点变成了尾节点它需要指向递归处理后的结果。用一句话概括就是反转前k个节点让反转后的尾节点指向剩余部分递归处理的结果然后返回反转后的新头节点。这个思路之所以成立是因为每一组的处理逻辑完全一样只是输入的起始位置不同。递归天然适合这种重复相同操作的场景。2.2 反转前k个节点的辅助函数在写主逻辑之前我们需要一个辅助函数它负责反转从某个节点开始的k个节点并返回新的头节点。这个函数的实现和整体反转几乎一样只是多了一个计数器来控制反转的数量。def reverse_k_nodes(head, k): prev None curr head count 0 while count k and curr: next_node curr.next curr.next prev prev curr curr next_node count 1 return prev注意这里的返回值是prev也就是反转后的新头节点。同时原来的head现在变成了尾节点它的next指向None。这一点非常重要因为后续拼接的时候需要用到这个尾节点。2.3 主递归函数的编写与拼接逻辑有了辅助函数之后主函数的逻辑就清晰了。首先检查剩余节点是否够k个如果不够就直接返回当前头节点。如果够就反转前k个然后递归处理剩下的最后把两段接起来。def reverse_k_group(head, k): if not head or k 1: return head # 检查剩余节点是否够k个 node head count 0 while node and count k: node node.next count 1 if count k: return head # 反转前k个节点 new_head reverse_k_nodes(head, k) # head现在是反转后的尾节点递归处理剩余部分并拼接 head.next reverse_k_group(node, k) return new_head这里有一个容易忽略的点在检查节点数量的时候node最终指向的是第k1个节点如果存在的话这个节点正好是下一组的起始位置。所以递归调用的时候直接传node就行了不需要额外计算。2.4 递归解法的空间复杂度分析递归解法看起来不需要额外的数据结构但实际上递归调用会在系统栈上占用空间。最坏情况下链表长度为n每k个一组递归深度大约是n/k。所以空间复杂度是O(n/k)在k1的时候退化为O(n)。这个空间开销在大多数场景下可以接受但如果链表特别长比如几十万个节点递归深度过大可能导致栈溢出。这也是为什么我在实际项目中更倾向于迭代解法的原因。3. 迭代解法的指针操作细节3.1 引入哨兵节点简化边界处理迭代解法最容易出错的地方就是头节点的处理。如果第一组反转后头节点变了你需要额外维护一个变量来记录新的头节点。为了避免这种麻烦我们引入一个哨兵节点dummy node让它指向原始头节点。哨兵节点的作用是把处理头节点和处理中间节点这两种情况统一起来。有了它之后每一组的反转和拼接逻辑完全一致不需要对第一组做特殊处理。dummy ListNode(0) dummy.next head group_prev dummygroup_prev表示每一组的前驱节点初始时指向哨兵节点。每一组处理完之后它会被更新为当前组的尾节点也就是下一组的前驱。3.2 定位每一组的起始和结束位置在反转一组之前我们需要先确认这一组是否有k个节点。做法是从group_prev开始往后走k步如果中途遇到None说明剩余节点不足k个直接返回结果。kth group_prev count 0 while kth and count k: kth kth.next count 1 if not kth: break走完之后kth指向这一组的第k个节点也就是这一组的尾节点。group_prev.next是这一组的头节点kth.next是下一组的头节点。3.3 逐组反转并重新拼接定位好之后就可以反转这一组了。反转的过程和整体反转一样但需要记录反转前的头节点反转后会变成尾节点和下一组的起始位置。group_next kth.next prev group_next curr group_prev.next while curr ! group_next: next_node curr.next curr.next prev prev curr curr next_node这段代码的巧妙之处在于prev初始化为group_next这样反转后的尾节点自然就指向了下一组的头节点省去了额外的拼接步骤。反转完成后prev指向这一组的新头节点group_prev.next需要更新为prev。同时原来的头节点变成了尾节点group_prev更新为它准备处理下一组。temp group_prev.next group_prev.next prev group_prev temp3.4 迭代解法的完整代码与测试验证把上面的步骤串起来完整的迭代解法如下def reverse_k_group_iterative(head, k): if not head or k 1: return head dummy ListNode(0) dummy.next head group_prev dummy while True: kth group_prev count 0 while kth and count k: kth kth.next count 1 if not kth: break group_next kth.next prev group_next curr group_prev.next while curr ! group_next: next_node curr.next curr.next prev prev curr curr next_node temp group_prev.next group_prev.next prev group_prev temp return dummy.next测试的时候我建议至少覆盖以下几种情况空链表、单节点链表、k1、k等于链表长度、k大于链表长度、链表长度正好是k的整数倍、链表长度不是k的整数倍。每一种情况都手动推演一遍预期结果再和代码输出对比。4. 那些让我调试了半天的边界情况4.1 最后一组不足k个节点时的处理这是最常见的坑。很多人的代码在处理最后一组的时候要么把不足k个的节点也反转了要么直接报空指针。正确的做法是在反转之前先检查剩余节点数量不足k个就保持原样。我在第一次写的时候检查逻辑写成了while node.next and count k结果当链表长度正好是k的时候node走到最后一个节点时node.next为None循环提前退出导致误判为不足k个。后来改成while node and count k就对了。注意检查节点数量的时候循环条件一定要用当前节点是否为None来判断而不是用当前节点的next是否为None。这两者在边界情况下的行为完全不同。4.2 指针断开后丢失后续节点反转链表的时候如果不提前保存next指针一旦执行curr.next prev后面的节点就找不到了。这个错误在整体反转里大家都会注意但在k个一组反转里因为多了分组逻辑更容易在拼接的时候忘记保存下一组的起始位置。我的经验是在任何修改next指针之前先把所有需要用的节点引用都保存到变量里。宁可多定义几个变量也不要在指针操作中间去取next。4.3 k值异常时的防御性编程虽然题目通常保证k是正整数但在实际工程中防御性编程是必要的。k1的时候直接返回原链表k大于链表长度的时候也直接返回原链表。这两个判断放在函数开头能省去很多后续的边界处理。另外如果链表为空也要直接返回None。这个判断看起来多余但如果没有后面的哨兵节点操作虽然不会报错但逻辑上是不必要的。5. 从这道题延伸出的链表操作通用技巧5.1 哨兵节点在链表题中的万能用法哨兵节点是链表题里最实用的技巧之一。凡是涉及头节点可能被修改的场景都可以用哨兵节点来简化逻辑。比如删除节点、合并链表、分割链表、反转链表全都能用。它的本质是用一个额外的节点把边界情况转化为一般情况。代价是多用一个节点的空间收益是代码逻辑更统一出错概率更低。这笔买卖在任何时候都划算。5.2 画图推演比空想高效十倍链表操作是空间想象力的考验但人的大脑并不擅长在脑子里维护多个指针的走向。我的习惯是拿一张纸画出节点和指针每执行一步就更新一次图。虽然前期慢但能帮你建立正确的直觉后期写代码的时候脑子里自然就有画面了。具体画法用方框表示节点箭头表示next指针用不同颜色的笔标注prev、curr、next三个指针的位置。每反转一个节点就擦掉旧箭头画新箭头。这个过程做上十道题链表操作基本就不会再出错了。5.3 递归与迭代的转换思路递归和迭代在链表题里经常可以互相转换。递归的本质是利用系统栈保存状态迭代的本质是手动维护状态变量。理解了这一点你就能在两种写法之间自由切换。转换的关键是找到递归函数里哪些变量在每一层调用中会变化然后把这些变量提取出来作为迭代的循环变量。比如这道题里递归函数的参数是当前组的头节点对应到迭代里就是group_prev.next。5.4 复杂度分析的实战意义很多人觉得复杂度分析只是面试时说说而已实际写代码用不上。但在这道题里复杂度分析直接影响了我的方案选择。递归解法空间复杂度是O(n/k)迭代是O(1)。如果链表长度是十万级别k2递归深度就是五万层大概率栈溢出。这种情况下迭代是唯一可行的方案。所以复杂度分析不是纸上谈兵它是在你选方案的时候给你提供决策依据的工具。6. 我在实际练习中总结的几条经验第一不要一上来就写代码。先画图先手动推演先把边界情况列出来。这个准备过程花五分钟能帮你省下半小时的调试时间。第二写完代码之后不要急着提交。自己构造几个测试用例包括空链表、单节点、k1、k大于长度、长度正好整除k、长度不整除k。手动推演预期结果再和代码输出对比。这个习惯能帮你发现百分之八十以上的边界错误。第三递归和迭代都要会写。面试的时候不一定考哪一种但两种都会写的人对问题的理解深度是完全不一样的。第四善用哨兵节点。链表题里百分之九十的边界问题都能用哨兵节点解决。养成习惯之后你会发现很多题目的难度直接降了一个档次。第五做完一道题之后试着把代码改一改看看能不能用更少的变量、更简洁的逻辑实现同样的功能。这个过程能帮你真正吃透指针操作的规律而不是死记硬背某一道题的解法。链表操作这件事说到底就是熟能生巧。k个一组反转只是其中一个典型的练习场景把这道题彻底搞明白之后你会发现其他链表题都变得有迹可循了。 
长河君 · 2026/10/16 5:46:03 · 阅读 1.2k K个一组反转链表：递归与迭代解法及边界处理
链表题在算法面试里出现频率极高而k个一组反转又是其中最能拉开差距的一类。它不像整体反转那样一趟走完就结束也不像两两交换那样规则固定它要求你在递归与迭代之间做出选择还要处理最后不足k个节点时的边界情况。很多人第一次写这道题代码在纸上推演没问题一跑就报空指针或者反转完发现链表断了、顺序乱了。这篇内容就把这道题从头到尾拆开讲清楚每一步为什么这么写以及我在实际练习中踩过的那些坑。1. 先搞清楚这道题到底在考什么1.1 题目本身的约束条件这道题的标准描述是给你一个链表的头节点每k个节点为一组进行反转返回修改后的链表。如果最后剩余的节点数量不足k个则保持它们原有的顺序。看起来简单但魔鬼藏在细节里。k1的时候什么都不用做k等于链表长度的时候等价于整体反转k大于链表长度的时候直接返回原链表。这三种边界情况如果不在脑子里过一遍写出来的代码大概率会在某个测试用例上挂掉。我个人的习惯是拿到任何链表题先在纸上画一个长度为6的链表然后分别用k2、k3、k4手动推演一遍。这个过程看起来笨但它能帮你在写代码之前就把指针的走向想清楚比上来就敲键盘效率高得多。1.2 为什么这道题比整体反转难整体反转链表只需要维护三个指针前驱、当前、后继一路走到底就行。但k个一组反转引入了分组的概念你需要在反转每一组之前先确认这一组是否有k个节点反转之后还要把上一组的尾节点和这一组的头节点接上同时把这一组的尾节点和下一组的头节点接上。换句话说整体反转只关心一条链而k个一组反转关心的是链与链之间的拼接关系。这就是为什么很多人单独写反转函数没问题但一拼接就出错。1.3 两种主流解法的取舍递归和迭代都能解这道题。递归的代码更简洁思路是反转前k个然后递归处理剩下的把两段接起来。迭代的代码稍长但不需要额外的栈空间在大规模数据下更稳妥。我在练习阶段建议两种都写一遍。递归帮你理解问题的分解方式迭代帮你掌握指针操作的精确性。面试的时候如果面试官没有特别要求选你写得最稳的那种就行。但如果你能主动说出两种解法的取舍那绝对是加分项。2. 递归解法的完整推导过程2.1 递归的核心思路拆解递归解法的本质是把一个大问题拆成两个子问题第一个子问题是反转当前这k个节点第二个子问题是处理剩余的链表。关键在于反转完当前这k个节点之后原来的头节点变成了尾节点它需要指向递归处理后的结果。用一句话概括就是反转前k个节点让反转后的尾节点指向剩余部分递归处理的结果然后返回反转后的新头节点。这个思路之所以成立是因为每一组的处理逻辑完全一样只是输入的起始位置不同。递归天然适合这种重复相同操作的场景。2.2 反转前k个节点的辅助函数在写主逻辑之前我们需要一个辅助函数它负责反转从某个节点开始的k个节点并返回新的头节点。这个函数的实现和整体反转几乎一样只是多了一个计数器来控制反转的数量。def reverse_k_nodes(head, k): prev None curr head count 0 while count k and curr: next_node curr.next curr.next prev prev curr curr next_node count 1 return prev注意这里的返回值是prev也就是反转后的新头节点。同时原来的head现在变成了尾节点它的next指向None。这一点非常重要因为后续拼接的时候需要用到这个尾节点。2.3 主递归函数的编写与拼接逻辑有了辅助函数之后主函数的逻辑就清晰了。首先检查剩余节点是否够k个如果不够就直接返回当前头节点。如果够就反转前k个然后递归处理剩下的最后把两段接起来。def reverse_k_group(head, k): if not head or k 1: return head # 检查剩余节点是否够k个 node head count 0 while node and count k: node node.next count 1 if count k: return head # 反转前k个节点 new_head reverse_k_nodes(head, k) # head现在是反转后的尾节点递归处理剩余部分并拼接 head.next reverse_k_group(node, k) return new_head这里有一个容易忽略的点在检查节点数量的时候node最终指向的是第k1个节点如果存在的话这个节点正好是下一组的起始位置。所以递归调用的时候直接传node就行了不需要额外计算。2.4 递归解法的空间复杂度分析递归解法看起来不需要额外的数据结构但实际上递归调用会在系统栈上占用空间。最坏情况下链表长度为n每k个一组递归深度大约是n/k。所以空间复杂度是O(n/k)在k1的时候退化为O(n)。这个空间开销在大多数场景下可以接受但如果链表特别长比如几十万个节点递归深度过大可能导致栈溢出。这也是为什么我在实际项目中更倾向于迭代解法的原因。3. 迭代解法的指针操作细节3.1 引入哨兵节点简化边界处理迭代解法最容易出错的地方就是头节点的处理。如果第一组反转后头节点变了你需要额外维护一个变量来记录新的头节点。为了避免这种麻烦我们引入一个哨兵节点dummy node让它指向原始头节点。哨兵节点的作用是把处理头节点和处理中间节点这两种情况统一起来。有了它之后每一组的反转和拼接逻辑完全一致不需要对第一组做特殊处理。dummy ListNode(0) dummy.next head group_prev dummygroup_prev表示每一组的前驱节点初始时指向哨兵节点。每一组处理完之后它会被更新为当前组的尾节点也就是下一组的前驱。3.2 定位每一组的起始和结束位置在反转一组之前我们需要先确认这一组是否有k个节点。做法是从group_prev开始往后走k步如果中途遇到None说明剩余节点不足k个直接返回结果。kth group_prev count 0 while kth and count k: kth kth.next count 1 if not kth: break走完之后kth指向这一组的第k个节点也就是这一组的尾节点。group_prev.next是这一组的头节点kth.next是下一组的头节点。3.3 逐组反转并重新拼接定位好之后就可以反转这一组了。反转的过程和整体反转一样但需要记录反转前的头节点反转后会变成尾节点和下一组的起始位置。group_next kth.next prev group_next curr group_prev.next while curr ! group_next: next_node curr.next curr.next prev prev curr curr next_node这段代码的巧妙之处在于prev初始化为group_next这样反转后的尾节点自然就指向了下一组的头节点省去了额外的拼接步骤。反转完成后prev指向这一组的新头节点group_prev.next需要更新为prev。同时原来的头节点变成了尾节点group_prev更新为它准备处理下一组。temp group_prev.next group_prev.next prev group_prev temp3.4 迭代解法的完整代码与测试验证把上面的步骤串起来完整的迭代解法如下def reverse_k_group_iterative(head, k): if not head or k 1: return head dummy ListNode(0) dummy.next head group_prev dummy while True: kth group_prev count 0 while kth and count k: kth kth.next count 1 if not kth: break group_next kth.next prev group_next curr group_prev.next while curr ! group_next: next_node curr.next curr.next prev prev curr curr next_node temp group_prev.next group_prev.next prev group_prev temp return dummy.next测试的时候我建议至少覆盖以下几种情况空链表、单节点链表、k1、k等于链表长度、k大于链表长度、链表长度正好是k的整数倍、链表长度不是k的整数倍。每一种情况都手动推演一遍预期结果再和代码输出对比。4. 那些让我调试了半天的边界情况4.1 最后一组不足k个节点时的处理这是最常见的坑。很多人的代码在处理最后一组的时候要么把不足k个的节点也反转了要么直接报空指针。正确的做法是在反转之前先检查剩余节点数量不足k个就保持原样。我在第一次写的时候检查逻辑写成了while node.next and count k结果当链表长度正好是k的时候node走到最后一个节点时node.next为None循环提前退出导致误判为不足k个。后来改成while node and count k就对了。注意检查节点数量的时候循环条件一定要用当前节点是否为None来判断而不是用当前节点的next是否为None。这两者在边界情况下的行为完全不同。4.2 指针断开后丢失后续节点反转链表的时候如果不提前保存next指针一旦执行curr.next prev后面的节点就找不到了。这个错误在整体反转里大家都会注意但在k个一组反转里因为多了分组逻辑更容易在拼接的时候忘记保存下一组的起始位置。我的经验是在任何修改next指针之前先把所有需要用的节点引用都保存到变量里。宁可多定义几个变量也不要在指针操作中间去取next。4.3 k值异常时的防御性编程虽然题目通常保证k是正整数但在实际工程中防御性编程是必要的。k1的时候直接返回原链表k大于链表长度的时候也直接返回原链表。这两个判断放在函数开头能省去很多后续的边界处理。另外如果链表为空也要直接返回None。这个判断看起来多余但如果没有后面的哨兵节点操作虽然不会报错但逻辑上是不必要的。5. 从这道题延伸出的链表操作通用技巧5.1 哨兵节点在链表题中的万能用法哨兵节点是链表题里最实用的技巧之一。凡是涉及头节点可能被修改的场景都可以用哨兵节点来简化逻辑。比如删除节点、合并链表、分割链表、反转链表全都能用。它的本质是用一个额外的节点把边界情况转化为一般情况。代价是多用一个节点的空间收益是代码逻辑更统一出错概率更低。这笔买卖在任何时候都划算。5.2 画图推演比空想高效十倍链表操作是空间想象力的考验但人的大脑并不擅长在脑子里维护多个指针的走向。我的习惯是拿一张纸画出节点和指针每执行一步就更新一次图。虽然前期慢但能帮你建立正确的直觉后期写代码的时候脑子里自然就有画面了。具体画法用方框表示节点箭头表示next指针用不同颜色的笔标注prev、curr、next三个指针的位置。每反转一个节点就擦掉旧箭头画新箭头。这个过程做上十道题链表操作基本就不会再出错了。5.3 递归与迭代的转换思路递归和迭代在链表题里经常可以互相转换。递归的本质是利用系统栈保存状态迭代的本质是手动维护状态变量。理解了这一点你就能在两种写法之间自由切换。转换的关键是找到递归函数里哪些变量在每一层调用中会变化然后把这些变量提取出来作为迭代的循环变量。比如这道题里递归函数的参数是当前组的头节点对应到迭代里就是group_prev.next。5.4 复杂度分析的实战意义很多人觉得复杂度分析只是面试时说说而已实际写代码用不上。但在这道题里复杂度分析直接影响了我的方案选择。递归解法空间复杂度是O(n/k)迭代是O(1)。如果链表长度是十万级别k2递归深度就是五万层大概率栈溢出。这种情况下迭代是唯一可行的方案。所以复杂度分析不是纸上谈兵它是在你选方案的时候给你提供决策依据的工具。6. 我在实际练习中总结的几条经验第一不要一上来就写代码。先画图先手动推演先把边界情况列出来。这个准备过程花五分钟能帮你省下半小时的调试时间。第二写完代码之后不要急着提交。自己构造几个测试用例包括空链表、单节点、k1、k大于长度、长度正好整除k、长度不整除k。手动推演预期结果再和代码输出对比。这个习惯能帮你发现百分之八十以上的边界错误。第三递归和迭代都要会写。面试的时候不一定考哪一种但两种都会写的人对问题的理解深度是完全不一样的。第四善用哨兵节点。链表题里百分之九十的边界问题都能用哨兵节点解决。养成习惯之后你会发现很多题目的难度直接降了一个档次。第五做完一道题之后试着把代码改一改看看能不能用更少的变量、更简洁的逻辑实现同样的功能。这个过程能帮你真正吃透指针操作的规律而不是死记硬背某一道题的解法。链表操作这件事说到底就是熟能生巧。k个一组反转只是其中一个典型的练习场景把这道题彻底搞明白之后你会发现其他链表题都变得有迹可循了。