第一次刷到“链表内指定区间反转”这道算法题时我的第一反应是我都会反转整个链表了你再让我反转其中一段这不是白送分吗结果真正动手去写才发现区间定位、指针交接、边界处理这些细节比想象中要阴险得多。这道题是LeetCode 92题也是各路“必刷基础算法题”清单里的常客它把单链表遍历、局部反转、重新拼接这三件事揉在一起正好卡在“入门”和“进阶”中间那道坎上。如果你正被这道题折磨或者想彻底把链表反转吃透这篇东西应该能帮你省不少时间。1. 这道题到底在考你什么题目理解与思路拆解1.1 题目描述与第一印象题目本身不长给你单链表的头节点head和两个整数left、right要求反转从位置left到位置right的链表节点位置从 1 开始计数。比如1 - 2 - 3 - 4 - 5left 2, right 4结果应该是1 - 4 - 3 - 2 - 5。很多人的第一印象和我一样先找到left位置的前一个节点然后从left遍历到right把这中间的一截“摘”下来反转再接回去。听起来就是“定位 反转 拼接”三个动作但实际写起来每一步都可能有意外定位多走一步会空指针反转完接回去接错节点会整个乱套left 1时头节点本身还会发生变化。这就是为什么这道题被公认为“整体反转的进阶版”——它考的不是你有没有背过反转模板而是你能不能在不破坏链表整体结构的前提下完成一次局部手术。1.2 考察点拆解把这道题的价值拆开看它至少覆盖了四个核心能力点。第一是链表遍历基本功。left和right是位置编号你需要通过指针步进来定位。这个动作看着简单但“走多少步”是新手最容易搞混的地方多走一步少走一步结果天差地别。第二是局部反转能力。反转整条链表时你从头开始三指针滚动就好但反转一个区间时区间内反转的“起点”和“终点”都是中途节点你不能简单地把head交给反转函数还要考虑前后怎么接。第三是边界处理敏感性。left 1意味着反转后头节点变了right 链表长度意味着区间尾部后面是null这些情况不处理代码要么崩要么结果错。第四是虚拟头节点技巧。为了统一处理“从头开始反转”和“从中间开始反转”两种情况通用解法会先创建一个虚拟头节点dummy让dummy.next head最后返回dummy.next。这个技巧在链表类题目里太常用了这道题是练熟它的绝佳素材。1.3 区间反转和整体反转的关系如果整体反转是单链表操作里的“入门动作”区间反转就是入门到进阶之间的台阶。它们不是两套独立的知识而是“基础反转 定位 接线”三个部分的组合拳。我建议你先把整条链表反转练到闭眼都能写出来的程度再来看区间反转。为什么因为区间反转无论选哪种解法内部核心都是在做局部反转区别只在于反转之前怎么定位、反转之后怎么把断开的链表重新缝上。基础不牢区间反转写出来一定到处是洞。2. 先把底层能力焊牢单链表反转的两种基础写法2.1 三指针迭代法单链表反转的迭代写法核心是三指针prev、cur、next。我当年学的时候有个困惑为什么要三个指针后来想明白了链表是单向结构当你把当前节点的next指向前一个节点时就断掉了往后走的唯一路径。所以必须在修改next之前先用一个临时指针把后面的节点抓住。三轮循环的状态大概是这样的初始时prev指向nullcur指向head每一轮先记下next cur.next然后把cur.next改成prev接着prev和cur同时前移一位循环直到cur变成null此时prev就是新链表的头。用生活里的例子类比就像你在一列火车上把每一节车厢的挂钩方向全部倒过来但必须先派人站在即将脱钩的那节车厢门口不然车厢就找不到了。代码很简单def reverse_list(head): prev None cur head while cur: next_node cur.next cur.next prev prev cur cur next_node return prev注意最后返回的是prev而不是cur很多人栽在这循环结束cur已经变成None真正的头节点是prev。2.2 递归反转递归写法代码更短但理解成本更高。核心思路是先递归反转到链表尾部然后在归的过程中让当前节点的下一个节点的next指回当前节点并把当前节点的next清空。基准情况是当前节点为空或只有一个节点直接返回该节点。def reverse_list_recursive(head): if not head or not head.next: return head new_head reverse_list_recursive(head.next) head.next.next head head.next None return new_head递归写法的好处是代码优雅不用手动管理指针坏处是递归调用栈深度为 O(n)当链表很长时可能爆栈。另外如果面试时你用递归一定要能把“归的过程中发生了什么”讲清楚否则面试官很容易判定你是背答案。2.3 基础反转代码为什么能在区间反转里复用区间反转最常见的一种解法就是直接把区间截出来当作一条“独立子链表”调用上面的反转函数然后再把它接回去。这样做的最大好处是你不必发明新的反转逻辑复用成熟代码错误率会低很多。不过在区间反转的场景里反转函数的输入是子链表的头节点。这个头节点到底是left_node还是right_node取决于你怎么“截取”区间。很多人在这里绕晕我的建议是把子链表反转前先画个图明确三个点区间前驱、区间头、区间尾。画明白了再动手。3. 指定区间反转的核心解法两种我实测过的高频写法3.1 写法一切断-反转-拼接思路最直白这种解法的流程分四步定位、切断、反转、拼接。适合理解优先的场景尤其适合刚学链表的新手。第一步创建dummy节点dummy.next head然后让一个指针pre从dummy出发移动left - 1步停在区间前驱节点上。第二步从pre出发继续移动right - left 1步让另一个指针right_node停在区间右端点上。同时记录left_node pre.next以及succ right_node.next也就是区间后面的第一个节点。第三步把子链表从原链表上断开pre.next Noneright_node.next None。此时left_node到right_node之间的节点成了一个独立链表。第四步调用基础反转函数把以left_node为头的子链表反转。反转后原来的right_node变成了新链表的头原来的left_node变成了新链表的尾。所以拼接时pre.next right_nodeleft_node.next succ整个链表缝合完毕。最后返回dummy.next。完整参考代码def reverse_between_cut(head, left, right): dummy ListNode(0, head) pre dummy for _ in range(left - 1): pre pre.next right_node pre for _ in range(right - left 1): right_node right_node.next left_node pre.next succ right_node.next pre.next None right_node.next None def reverse(head): prev None cur head while cur: nxt cur.next cur.next prev prev cur cur nxt return prev new_head reverse(left_node) pre.next new_head left_node.next succ return dummy.next这个写法的坑主要在接线顺序反转之后left_node已经不是子链表的头了它变成了尾部所以是left_node.next succ。如果写成pre.next left_node链表就会出现环而且在 LeetCode 上直接超时或死循环。3.2 写法二一次遍历头插法面试最推荐第二种解法我后来刷题时用得越来越多因为它只需要一次遍历、不需要额外写反转函数、也不需要在反转后再做复杂的接线判断。核心思路是定位到区间前驱之后固定前驱不动把区间内每个“下一个节点”依次摘下来插入到前驱的后面。每插入一个这个节点在区间内的相对顺序就被翻转到最前面循环right - left次之后区间就反转完了。这个过程很像“头插法建链表”所以叫头插法。它比切断法更考验对指针状态的理解但代码短、逻辑紧凑、不容易漏接线。def reverse_between(head, left, right): dummy ListNode(0, head) pre dummy for _ in range(left - 1): pre pre.next cur pre.next for _ in range(right - left): nxt cur.next cur.next nxt.next nxt.next pre.next pre.next nxt return dummy.next我一行一行拆给你看。循环开始前pre停在区间前驱cur是区间第一个节点。第一轮循环nxt记为cur.next也就是区间第二个节点cur.next nxt.next相当于把第二个节点从它原来的位置摘掉让第一个节点直接连到第三个节点nxt.next pre.next把摘下来的节点指向当前的第一个节点pre.next nxt让前驱指向这个被摘下来的节点。这一步完成之后原区间第二个节点被放到了区间最前面成为新的“第一个节点”。第二轮再摘第三个节点插到最前面……如此反复区间就反转了而且cur始终是指向区间当前第一个节点这里要特别注意cur在过程中并没有变化它一直是指向“原来区间第一个节点”的那个指针只是它的next被不断修改相当于它变成了区间的尾部候选节点。这个写法的精妙之处在于它从头到尾没有切断过链表所有连接都是通过修改next指针完成的中间不存在null断开阶段所以不需要额外处理succ的保存。这也是为什么面试官通常更喜欢这种解法——代码短、不易错、能体现对链表指针的掌控力。3.3 两种写法怎么选对比与场景建议用一张表把两种解法的特点摆清楚。对比维度切断-反转-拼接一次遍历头插法理解门槛较低流程直观较高需要推演头插过程代码长度较长需额外反转函数短约十行遍历次数两次定位 一次反转一次定位 区间内一次遍历边界风险接线顺序容易搞混逻辑紧凑不易漏接面试建议新手阶段先用熟练后主推我的建议是初学阶段两种都写一遍先用切断法理解“局部反转 拼接”的宏观过程再用头插法感受一下“边遍历边调整”的微观操作。面试时如果时间紧直接上头插法如果面试官追问思路先用切断法讲设计再展示头插法代码会显得你理解更全面。4. 边界情况与易错点这些坑我全都踩过4.1 left1 时头节点的身份变化left 1意味着反转区间从链表头开始反转完成后整个链表的头节点会变成原来的第right个节点。如果不做任何处理直接返回原来的head结果一定错。虚拟头节点dummy就是用来治这个问题的。dummy.next初始是head无论后续指针怎么改最终整个新链表的头一定是dummy.next你永远不需要关心“头节点是不是变了”。这不只是这道题的好习惯凡是有可能修改头节点的链表题我都会条件反射地加一个dummy能省掉一大半边界情况的讨论。有人会问那题目规定不能用额外节点怎么办后面我会专门讲不带头节点的情况。但你先记住结论允许的情况下dummy是优先选择。4.2 区间长度等于1不需要任何特殊处理如果left right反转一个节点等于没反转。切断解法里子链表只有一个节点反转函数也能正常工作头插法解法里right - left 0循环一次都不执行直接返回dummy.next。两种写法天然兼容无需额外判断。所以如果你的代码在left right时出了问题大概率是循环次数写错了比如把range(right - left 1)当成range(right - left)来用多反转了一次。4.3 反转后的接线顺序为什么是事故高发区我在给朋友 review 代码时发现最容易写错的地方就是切断法里反转后的那两句接线。反转前pre.next是left_noderight_node.next是succ。反转后right_node成了新头left_node成了新尾。于是正确的接线是pre.next right_node和left_node.next succ。有人觉得别扭明明反转前left_node在right_node前面为什么反转后反过来了因为你把子链表当成独立链表去反转了反转函数本身不关心它在原链表中的位置它只负责把传入的头变成尾。想通这一点接线就顺了。另一个防止写错的方法是想象你把一整串珠子倒过来原来在左边的珠子现在到了右边你接回原链时接的是“倒过来之后的两端”而不是“原来的两端”。4.4 关于虚拟头节点的两个共识第一创建dummy时它的next必须指向head返回时必须返回dummy.next而不是dummy本身。第二dummy只承担“占位”职责它的值无所谓通常给0或者-1都行。我在早期写代码时犯过一个低级错误创建了dummy却把pre初始化为head而不是dummy结果left 1时pre根本无法定位到区间前驱。记住因为位置从 1 开始计数left 1时前驱是dummy只有把pre从dummy出发走left - 1步这个设定才对所有left统一生效。5. 常见问题与调试技巧实录5.1 空指针异常九成是定位指针多走了一步用 Python 写的时候报错一般是AttributeError: NoneType object has no attribute next用 Java 写就是NullPointerException。碰到这种错误第一反应不是去看反转逻辑而是先检查定位循环。比如找区间前驱正确写法是从dummy出发走left - 1步。如果写成range(left)或range(left 1)就多走了一步pre可能就悬在null上。我的排查习惯是在定位循环的前后各打印一次当前节点的值确认pre、cur停在哪个位置动手改代码之前先确认是不是定位问题。5.2 结果不对先用手边用例做回归结果不对的情况比空指针更隐蔽。常见的表现有链表没有发生反转、反转的区间不对、反转后链表丢了一段、输出里出现循环导致超时。为了快速排查我会准备一个本地打印函数def print_list(head): res [] while head: res.append(str(head.val)) head head.next print( - .join(res))每写完一个版本先用几个手边用例跑一遍。如果输出和预期不一致我就把“反转前、定位时、反转后”三个时间点的链表状态都打出来定位是哪个环节出了问题。比如反转区间没问题但整个链表丢了后半段多半是succ没保存好如果是循环超时则要怀疑某个节点的next指回了自己形成了环。5.3 我长期使用的自测用例清单这道题我建议用下面几组用例做回归覆盖绝大多数边界。用例leftright预期输出[1]11[1][1, 2]12[2, 1][1, 2, 3, 4, 5]24[1, 4, 3, 2, 5][1, 2, 3, 4, 5]15[5, 4, 3, 2, 1][3, 5]12[5, 3][1, 2, 3, 4, 5]33[1, 2, 3, 4, 5]第一组测单节点第二组测反转整条短链表第三组是标准中间反转第四组测从头反转到底第五组测双节点完整反转第六组测区间长度为 1。能把这几组全跑通这道题的实现基本就稳了。5.4 复杂度分析为什么迭代法更吃香两种主流解法的时空复杂度是一致的时间上需要先遍历到left位置再处理区间内的节点总体是 O(n)空间上是 O(1)因为只用了常数个指针变量没有借助额外容器。相比之下如果用递归反转子链表虽然代码更短但递归深度与链表长度相关最坏情况下空间复杂度会变成 O(n)。我在面试中会主动提一句这个对比既显示对复杂度的理解也解释自己为什么倾向迭代解法。刷这道题的时候把复杂度养成条件反射后续遇到进阶题会轻松很多。6. 进阶路径与变式扩展6.1 从区间反转到K个一组翻转如果你把指定区间反转写顺了LeetCode 25题“K个一组翻转链表”可以当作下一个练兵场。那道题的要求是每 K 个节点一组进行反转最后一组如果不足 K 个保持不变。它本质上就是“多次执行区间反转”只是每次的left和right要根据K动态计算并且处理完一组后要移动指针到下一组的前驱。我在做那道题时的体会是区间反转里练出来的“定位前驱”和“拼接”能力几乎是原样迁移。区别只是每次处理完一组要把pre移到这一组的尾部当作下一组的前驱。如果区间反转的代码是你自己写的而不是背的到了这一步会非常顺。6.2 循环链表与不带头结点的场景热词里出现了“循环单链表”和“不带头结点的单链表”这两个方向也值得提一嘴。循环链表的区间反转有个明显区别区间的尾部后面不是null而是会绕回头节点所以反转完成后不能让尾节点的next指向null而是要接回环上的下一个节点。处理思路和单链表一致但每一步都要想清楚“这个节点的 next 是否允许为 null”。不带头节点的情况则是一个经典的面试陷阱如果题目明确规定不能使用dummy那left 1时必须单独处理头节点的更新。解法是反转后返回新链表的头函数签名可能变成“返回新头”而不是在内部直接改。这个场景能帮你理解dummy到底省了什么事——它本质上是把“头节点变化”的特例统一成了常规情况。6.3 这道题在工程实践中的意义有人觉得链表反转这类题目面试以外用不到其实不然。凡是涉及底层内存操作、嵌入式代码、缓存淘汰算法的地方指针和引用的操作逻辑都和链表反转高度相似。比如 LRU 缓存的节点移动、内核链表里的节点摘除与插入背后都是“找到前驱、修改 next、重新连接”这套动作。把这道题练熟提升的不只是刷题手感而是对“通过引用操作数据”这种底层思维模式的敏感度。真到排查线上空指针问题时你会感谢当年画过的那几张链表示意图。我在实际带人的过程中发现能不看答案写出区间反转的人写其他链表题的时候明显更稳因为他们已经在心里建立了一个完整的“指针状态机”每一个next修改前后的状态都是清晰的。这种能力不是靠背代码得来的就是靠一遍一遍画图、推演、踩坑积累起来的。