LeetCode 92题是我在刷链表题时觉得最值得反复琢磨的一道。如果你刷过LeetCode 206题反转整个链表再来看这道“反转链表II”会发现它其实是把反转动作限定在一个区间内难度直接从“入门”跳到了“必须熟练”。面试里这道题出现频率相当高因为它精准地考察了三个东西链表节点的指针操作、边界条件的处理、以及代码实现时的手感。很多人在白板上写这道题思路能说清楚一动手就崩崩的地方基本都集中在指针更新顺序和虚拟头节点的处理上。这篇文章我不打算只贴一个答案了事而是把这道题彻底拆开从题目到底在考什么、两种主流解法的推导过程、代码实现细节到常见错误和扩展变体一次性讲透。无论你是刚开始刷LeetCode还是准备面试前突击链表专题这篇都值得收藏下来反复看。1. 题目到底在考什么先看懂LeetCode 92题1.1 题目描述与输入输出格式先过一遍原题。给定单链表的头节点head和两个整数left、right要求反转从位置left到位置right的链表节点返回反转后的链表。注意这里的left和right是从 1 开始计数的。举个最经典的例子输入head [1,2,3,4,5], left 2, right 4 输出[1,4,3,2,5]也就是说原始链表是 1-2-3-4-5把第 2 个节点到第 4 个节点这一小段2-3-4反转成 4-3-2再接回原链表得到 1-4-3-2-5。还有一个先决条件1 left right nn 是链表长度。这意味着输入不用考虑区间越界的问题。这道题常见的进阶要求是一次遍历完成。也就是说你不能先把链表转成数组、反转区间再建链那样虽然也能过但面试官基本会追问“能不能一次遍历空间复杂度 O(1)”所以直接按最优解来写才是正路。1.2 这道题为什么是面试高频考点拆解很多人刷题喜欢按题号顺序刷刷到92题时往往已经被前面的链表题折磨得够呛。但我想说的是92题在整个链表题型里是一个“分水岭”。它会同时考察你以下这几个能力指针操作的精确性。链表反转本质上就是不断修改节点的next指向。全量反转只需要维护两个指针但区间反转要额外记录区间的“前驱节点”和“后继节点”相当于在一串珍珠项链里精准地挑出一段翻转后再接回去手一抖就散架。边界条件的敏感度。left 1时反转区间包含头节点这时候如果没有虚拟头节点处理起来会非常别扭right n时区间后面没有节点了也要保证代码不出错。面试官非常喜欢把这两个边界条件单独拿出来考你。代码的简洁性和健壮性。这道题解法不止一种但最优雅的“头插法”只需要一个 for 循环就能完成反转。能在白板上写出简洁且不容易出错的版本是面试官判断你代码能力的重要依据。换句话说刷透这道题你等于同时复习了 206 题反转链表、需要额外处理边界场景的区间操作也为后面刷 25 题K 个一组翻转链表打下了基础。2. 解题前的关键认知链表反转的三种形态在动手写代码之前有几个底层认知必须先建立起来不然你只是背代码换个题目就废。2.1 从206题到92题全量反转 vs 区间反转先回顾一下 206 题的反转逻辑。全量反转链表的经典迭代写法是prev None curr head while curr: nxt curr.next curr.next prev prev curr curr nxt return prev这段代码的核心思路是每次把当前节点的next指向前一个节点然后三个指针整体向后移动。循环结束后prev就是新链表的头节点。92 题可以看成是 206 题的“局部版本”。差别在于206 题从头到尾都在反转而 92 题只反转中间某一段。这就引出了两个额外需求需要找到反转区间的“前驱节点”pre也就是left位置的前一个节点反转完区间后需要把区间的头部接回pre区间的尾部接回原来的后继节点succ。所以整体思路是定位 - 反转区间 - 重新连接。听起来不复杂但实现细节决定成败。2.2 虚拟头节点 dummy 为什么必不可少关于虚拟头节点dummy node我见过太多人一开始不理解它的意义直到在left 1时把自己卡死。当left 1时反转区间从链表头节点开始。此时区间前面没有任何节点执行“定位 pre”这步时根本没有pre可找。如果强行特判代码就会变得非常啰嗦。解决办法就是人为造一个哨兵节点dummy ListNode(-1) dummy.next head这个dummy节点不存储有效数据只用来占位置。这样一来无论left 1还是left 1pre永远都存在。最终返回结果时只需要返回dummy.next它一定指向处理完之后链表的真实头节点。记住一个套路只要链表操作可能涉及头节点的变更就无脑加虚拟头节点。这是一个可以帮你省掉大量边界讨论的习惯。2.3 一次遍历的核心三指针的接力92 题的高频进阶要求是一次遍历完成。这意味着你不能先遍历找到right位置再回头处理而是在从头走到尾的过程中就把反转做掉。这里要引入一个核心的三指针模型pre、cur、nxt。pre永远指向反转区间前一个节点也就是反转区间的“锚点”它不会移动cur始终指向当前待处理区间内的第一个节点最初是left位置的节点注意这里说的是“始终”它不会在循环里推进nxt是cur.next也就是每次要被“摘走”并移动到区间前端的那个节点。理解了这个模型头插法的代码就只剩一个动作不断把nxt从cur后面摘下来插到pre的后面。这个过程重复right - left次区间就反转完了。很多同学死活看不懂头插法的 for 循环就是没意识到cur在整个过程中一直在向右“后退”——不对应该说cur的位置没变变的是它后面挂的节点被逐个摘走。用例子走一遍立刻就会明白。3. 两种主流通解穿针引线与头插法这道题网上常见的有两种解法一种是“穿针引线法”也叫“先定位再断开反转”另一种是“头插法”。两种思路都值得掌握因为它们分别对应了不同的思考角度而且面试中你很可能会被要求说出多种解法。3.1 方法一先定位再断链穿针引线法穿针引线法的核心思想比较直白把反转区间单独拆下来反转完再接回去。具体步骤是用pre指针走到left前一个节点用两个指针left_node和right_node锁定反转区间的左右端点记录区间后面的节点succ把区间从原链表上“剪”下来让pre.next Noneright_node.next None对区间链表调用 206 题的反转函数返回新的头节点重新缝合pre.next right_node反转后右端点变成了新区间头left_node.next succ。这个方法思路清晰每一步都对应一个直观的操作尤其适合在讲解时让别人听懂。但它的缺点是代码较长需要额外实现一个反转函数而且断链和重连的过程要非常小心否则容易丢节点。3.2 方法二头插法推荐解法头插法是我个人最推荐的做法也是面试时写起来最快的版本。它不需要把区间拆下来而是在一次遍历中不断把当前节点后面的节点“挪”到pre的后面效果上和区间反转完全一致。模拟一下经典用例left 2, right 4链表初始状态是dummy - 1 - 2 - 3 - 4 - 5第一步pre移动到 1cur指向 2。此时要把 3 插到 1 的后面得到dummy - 1 - 3 - 2 - 4 - 5。第二步继续把 4 插到 1 的后面得到dummy - 1 - 4 - 3 - 2 - 5。此时区间2 - 3 - 4已经被原地反转成了4 - 3 - 2整个过程只遍历了两个节点代码里唯一的指针移动就在这几次“摘下和插入”中。头插法的好处是空间复杂度 O(1)且只做了一次遍历pre走到左侧端点的那一轮不算额外遍历因为链表头部操作本身就需要走到定位点。代码量也不大后面我会给出完整实现。3.3 复杂度分析与对比维度穿针引线法头插法时间复杂度O(n)需要遍历链表定位O(n)一次遍历完成空间复杂度O(1)不计递归栈O(1)代码量较长需额外反转函数较短单函数完成边界处理需要切断再缝合易漏指针只需要正确管理 pre.next 和 cur.next面试表现思路直观但实现易错简洁高效推荐优先写这个如果你在 LeetCode 上做题两个方法都能通过。但如果是在面试现场给你 10 分钟手写我会毫不犹豫选头插法。4. 实操过程与代码实现一步步手写核心解法光讲思路不行代码得能跑。这一节我给出头插法的完整实现并逐步解析每一行的含义。老规矩以 Python 为主再给一个 Java 版本做对照。4.1 Python 版完整代码与逐行解析# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def reverseBetween(self, head: ListNode, left: int, right: int) - ListNode: dummy ListNode(-1) dummy.next head pre dummy # 第 1 步让 pre 走到 left 的前一个节点 for _ in range(left - 1): pre pre.next # cur 指向反转区间的第一个节点它只负责“向后看” cur pre.next # 第 2 步头插法执行 right - left 次 for _ in range(right - left): nxt cur.next # 1. 先把 cur 后面的节点摘出来 cur.next nxt.next # 2. 让 cur 跨过 nxt直接连到 nxt 后面 nxt.next pre.next # 3. 让 nxt 指向 pre 后面的第一个节点 pre.next nxt # 4. 再把 nxt 接到 pre 的后面 return dummy.next逐行拆解一下这里的重点dummy节点的作用是统一处理left 1的情况不解释太多直接当固定套路记住。for _ in range(left - 1)让pre从dummy开始移动到第left - 1个节点。比如left 2pre移动 1 步正好指向节点 1。cur指向pre.next也就是left位置的那个节点。这个节点在整个过程中不向前移动每次循环只是把它后面的节点摘走。循环次数是right - left这很关键。比如区间长度是 3left2, right4只需要反转两次因为第一次把第 3 个节点挪到前面第二次把第 4 个节点挪到前面原本第 2 个节点自然就被挤到最后了。4.2 Java 版本对照实现/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { public ListNode reverseBetween(ListNode head, int left, int right) { ListNode dummy new ListNode(-1); dummy.next head; ListNode pre dummy; for (int i 0; i left - 1; i) { pre pre.next; } ListNode cur pre.next; for (int i 0; i right - left; i) { ListNode nxt cur.next; cur.next nxt.next; nxt.next pre.next; pre.next nxt; } return dummy.next; } }Java 版和 Python 版逻辑完全一致。面试时如果允许选语言我一般优先写 Python代码短、不容易写错但有些公司要求用 Java那也不慌逻辑是一样的只是语法换了皮。4.3 边界用例验证left1 和 right链表末尾这段一定要自己推一遍尤其是left 1时的执行过程。比如head [3,5], left 1, right 2初始化dummy - 3 - 5pre dummypre移动left - 1 0步所以pre仍然指向dummycur pre.next也就是节点 3循环right - left 1次nxt cur.next即节点 5cur.next nxt.next即节点 5 的 next为 None所以3.next Nonenxt.next pre.next即5.next 3pre.next nxt即dummy.next 5。最终链表是5 - 3返回dummy.next正确。再看right 链表末尾的情况比如head [1,2,3], left 1, right 3。此时效果等价于整个链表反转代码同样能正确处理。因为nxt每次摘取的都是cur.next当区间到达末尾时cur.next会变成 Nonenxt.next pre.next也照样执行不会产生空指针异常。5. 常见问题与排查技巧实录不管我写多少遍这道题总能在评论区看到几乎相同的几个问题。这里集中整理一下每个问题都是真实的踩坑经历。5.1 循环终止条件写错到底执行几次我看到的最常见错误就是把第二个 for 循环的次数写成right - left 1甚至right - left 2。记住反转区间left到right本质上只需要把区间内除了第一个节点以外的right - left个节点逐个提到最前面。比如 2 到 4除了第 2 个节点 2 本身还需要把节点 3 和节点 4 各提一次所以是 2 次也就是4 - 2 2。如果写成1第一次循环后链表就已经多处理了一个节点后面再循环下去就会把已经反转好的节点又挪动一次最终结果完全乱掉。5.2 指针更新顺序记不住先取 nxt再动 cur.next头插法四行代码里最核心也是最容易出错的一点是先保存nxt再修改nxt.next或cur.next。一旦你先改了cur.next你后面就找不到nxt了链表直接断掉。我用一句话记住这个顺序“先摘后接先记后改”。具体到代码里就是先记下nxt cur.next让cur跳过nxtcur.next nxt.next让nxt指向pre后面的节点把nxt挂在pre后面。第 3、4 步的顺序也不能颠倒。如果先执行pre.next nxt那pre.next就变成了nxt此时再执行nxt.next pre.next就让nxt.next指向了它自己形成环。这一步我至少看到五六个人在评论区问过为什么“链表变成环了”基本都是这个原因。5.3 易错点速查表易错点正确姿势left 1时没有虚拟头节点一律先建dummy返回dummy.next第二个循环写right-left1次严格写right-left次先改cur.next再取nxt先nxt cur.next再改指针nxt.next和pre.next的赋值顺序颠倒必须先nxt.next pre.next再pre.next nxt结束时cur有没有前进不需要cur位置不变变的是它后面连接的节点返回head还是dummy.next统一返回dummy.next防止头节点被换掉6. 从一道题刷穿一类题链表题的通用套路刷题最忌讳的就是一题一题地背答案而是要形成“题型意识”。92 题一旦吃透你会发现很多题目都是它的变体。6.1 与25题 K 个一组翻转链表的关联LeetCode 25 题要求每 K 个节点一组进行翻转。这个题本质上就是反复调用“区间反转”的能力。只需要把链表按 K 个一组划分对每一组执行区间反转然后处理好组与组之间的连接即可。如果 92 题你能裸写出来25 题你就只需要额外考虑两个点怎么确定一组的起始位置以及怎么把上一组的尾巴接到下一组的头上。反过来说如果 92 题还卡着25 题基本不会顺畅。另外LeetCode 24 题两两交换链表中的节点可以看成是 K2 的 25 题也是区间反转的一种特殊形态。6.2 面试中如何快速给出手写代码面试手写链表题我有一个固定的节奏先画图把pre、cur、nxt标出来确定循环步骤写dummy节点直接避开头节点变更问题写出定位pre的循环写出头插法的四行核心交换逻辑测两个边界用例left 1和right n最后再口头跟面试官确认一下时间复杂度和空间复杂度。这套流程走下来基本不会翻车。尤其是第 5 步很多人写出了代码就觉得万事大吉结果面试官随手改一个参数代码就崩了。养成“写完就测边界”的习惯能让你在面试里显得非常专业。6.3 扩展思考递归写法与原地算法92 题除了迭代写法也可以用递归实现区间反转。递归的核心思想是“递归到 right 位置后开始逐个返回并调整指针”代码很简洁但理解成本会高一些。我个人建议优先掌握迭代写法递归作为进阶内容面试时如果不问就不主动写。另外这道题完全可以纯原地完成不需要额外开辟数组或者其他数据结构。在 LeetCode 上这道题的官方题解和热门题解也都强调 O(1) 空间复杂度。遇到任何说“这个题必须用额外空间才能做”的说法都要打个问号。把 92 题刷透之后建议再花一天时间刷掉这几个关联题206 题反转整个链表、24 题两两交换节点、25 题K 个一组翻转。你会发现这些题之间有一个非常清晰的递进关系而 92 题正是整个链条里承上启下的关键一环。我个人在实际练习中的体会是链表题最考验的就是“指针修改顺序”的肌肉记忆。一道 92 题如果能在不看答案的情况下15 分钟内手写出来并一次性通过所有测试用例那么链表这一关你基本算是站稳了。别急着追求刷题数量先把这道题吃透后面的路会顺畅很多。
LeetCode 92题是我在刷链表题时觉得最值得反复琢磨的一道。如果你刷过LeetCode 206题反转整个链表再来看这道“反转链表II”会发现它其实是把反转动作限定在一个区间内难度直接从“入门”跳到了“必须熟练”。面试里这道题出现频率相当高因为它精准地考察了三个东西链表节点的指针操作、边界条件的处理、以及代码实现时的手感。很多人在白板上写这道题思路能说清楚一动手就崩崩的地方基本都集中在指针更新顺序和虚拟头节点的处理上。这篇文章我不打算只贴一个答案了事而是把这道题彻底拆开从题目到底在考什么、两种主流解法的推导过程、代码实现细节到常见错误和扩展变体一次性讲透。无论你是刚开始刷LeetCode还是准备面试前突击链表专题这篇都值得收藏下来反复看。1. 题目到底在考什么先看懂LeetCode 92题1.1 题目描述与输入输出格式先过一遍原题。给定单链表的头节点head和两个整数left、right要求反转从位置left到位置right的链表节点返回反转后的链表。注意这里的left和right是从 1 开始计数的。举个最经典的例子输入head [1,2,3,4,5], left 2, right 4 输出[1,4,3,2,5]也就是说原始链表是 1-2-3-4-5把第 2 个节点到第 4 个节点这一小段2-3-4反转成 4-3-2再接回原链表得到 1-4-3-2-5。还有一个先决条件1 left right nn 是链表长度。这意味着输入不用考虑区间越界的问题。这道题常见的进阶要求是一次遍历完成。也就是说你不能先把链表转成数组、反转区间再建链那样虽然也能过但面试官基本会追问“能不能一次遍历空间复杂度 O(1)”所以直接按最优解来写才是正路。1.2 这道题为什么是面试高频考点拆解很多人刷题喜欢按题号顺序刷刷到92题时往往已经被前面的链表题折磨得够呛。但我想说的是92题在整个链表题型里是一个“分水岭”。它会同时考察你以下这几个能力指针操作的精确性。链表反转本质上就是不断修改节点的next指向。全量反转只需要维护两个指针但区间反转要额外记录区间的“前驱节点”和“后继节点”相当于在一串珍珠项链里精准地挑出一段翻转后再接回去手一抖就散架。边界条件的敏感度。left 1时反转区间包含头节点这时候如果没有虚拟头节点处理起来会非常别扭right n时区间后面没有节点了也要保证代码不出错。面试官非常喜欢把这两个边界条件单独拿出来考你。代码的简洁性和健壮性。这道题解法不止一种但最优雅的“头插法”只需要一个 for 循环就能完成反转。能在白板上写出简洁且不容易出错的版本是面试官判断你代码能力的重要依据。换句话说刷透这道题你等于同时复习了 206 题反转链表、需要额外处理边界场景的区间操作也为后面刷 25 题K 个一组翻转链表打下了基础。2. 解题前的关键认知链表反转的三种形态在动手写代码之前有几个底层认知必须先建立起来不然你只是背代码换个题目就废。2.1 从206题到92题全量反转 vs 区间反转先回顾一下 206 题的反转逻辑。全量反转链表的经典迭代写法是prev None curr head while curr: nxt curr.next curr.next prev prev curr curr nxt return prev这段代码的核心思路是每次把当前节点的next指向前一个节点然后三个指针整体向后移动。循环结束后prev就是新链表的头节点。92 题可以看成是 206 题的“局部版本”。差别在于206 题从头到尾都在反转而 92 题只反转中间某一段。这就引出了两个额外需求需要找到反转区间的“前驱节点”pre也就是left位置的前一个节点反转完区间后需要把区间的头部接回pre区间的尾部接回原来的后继节点succ。所以整体思路是定位 - 反转区间 - 重新连接。听起来不复杂但实现细节决定成败。2.2 虚拟头节点 dummy 为什么必不可少关于虚拟头节点dummy node我见过太多人一开始不理解它的意义直到在left 1时把自己卡死。当left 1时反转区间从链表头节点开始。此时区间前面没有任何节点执行“定位 pre”这步时根本没有pre可找。如果强行特判代码就会变得非常啰嗦。解决办法就是人为造一个哨兵节点dummy ListNode(-1) dummy.next head这个dummy节点不存储有效数据只用来占位置。这样一来无论left 1还是left 1pre永远都存在。最终返回结果时只需要返回dummy.next它一定指向处理完之后链表的真实头节点。记住一个套路只要链表操作可能涉及头节点的变更就无脑加虚拟头节点。这是一个可以帮你省掉大量边界讨论的习惯。2.3 一次遍历的核心三指针的接力92 题的高频进阶要求是一次遍历完成。这意味着你不能先遍历找到right位置再回头处理而是在从头走到尾的过程中就把反转做掉。这里要引入一个核心的三指针模型pre、cur、nxt。pre永远指向反转区间前一个节点也就是反转区间的“锚点”它不会移动cur始终指向当前待处理区间内的第一个节点最初是left位置的节点注意这里说的是“始终”它不会在循环里推进nxt是cur.next也就是每次要被“摘走”并移动到区间前端的那个节点。理解了这个模型头插法的代码就只剩一个动作不断把nxt从cur后面摘下来插到pre的后面。这个过程重复right - left次区间就反转完了。很多同学死活看不懂头插法的 for 循环就是没意识到cur在整个过程中一直在向右“后退”——不对应该说cur的位置没变变的是它后面挂的节点被逐个摘走。用例子走一遍立刻就会明白。3. 两种主流通解穿针引线与头插法这道题网上常见的有两种解法一种是“穿针引线法”也叫“先定位再断开反转”另一种是“头插法”。两种思路都值得掌握因为它们分别对应了不同的思考角度而且面试中你很可能会被要求说出多种解法。3.1 方法一先定位再断链穿针引线法穿针引线法的核心思想比较直白把反转区间单独拆下来反转完再接回去。具体步骤是用pre指针走到left前一个节点用两个指针left_node和right_node锁定反转区间的左右端点记录区间后面的节点succ把区间从原链表上“剪”下来让pre.next Noneright_node.next None对区间链表调用 206 题的反转函数返回新的头节点重新缝合pre.next right_node反转后右端点变成了新区间头left_node.next succ。这个方法思路清晰每一步都对应一个直观的操作尤其适合在讲解时让别人听懂。但它的缺点是代码较长需要额外实现一个反转函数而且断链和重连的过程要非常小心否则容易丢节点。3.2 方法二头插法推荐解法头插法是我个人最推荐的做法也是面试时写起来最快的版本。它不需要把区间拆下来而是在一次遍历中不断把当前节点后面的节点“挪”到pre的后面效果上和区间反转完全一致。模拟一下经典用例left 2, right 4链表初始状态是dummy - 1 - 2 - 3 - 4 - 5第一步pre移动到 1cur指向 2。此时要把 3 插到 1 的后面得到dummy - 1 - 3 - 2 - 4 - 5。第二步继续把 4 插到 1 的后面得到dummy - 1 - 4 - 3 - 2 - 5。此时区间2 - 3 - 4已经被原地反转成了4 - 3 - 2整个过程只遍历了两个节点代码里唯一的指针移动就在这几次“摘下和插入”中。头插法的好处是空间复杂度 O(1)且只做了一次遍历pre走到左侧端点的那一轮不算额外遍历因为链表头部操作本身就需要走到定位点。代码量也不大后面我会给出完整实现。3.3 复杂度分析与对比维度穿针引线法头插法时间复杂度O(n)需要遍历链表定位O(n)一次遍历完成空间复杂度O(1)不计递归栈O(1)代码量较长需额外反转函数较短单函数完成边界处理需要切断再缝合易漏指针只需要正确管理 pre.next 和 cur.next面试表现思路直观但实现易错简洁高效推荐优先写这个如果你在 LeetCode 上做题两个方法都能通过。但如果是在面试现场给你 10 分钟手写我会毫不犹豫选头插法。4. 实操过程与代码实现一步步手写核心解法光讲思路不行代码得能跑。这一节我给出头插法的完整实现并逐步解析每一行的含义。老规矩以 Python 为主再给一个 Java 版本做对照。4.1 Python 版完整代码与逐行解析# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def reverseBetween(self, head: ListNode, left: int, right: int) - ListNode: dummy ListNode(-1) dummy.next head pre dummy # 第 1 步让 pre 走到 left 的前一个节点 for _ in range(left - 1): pre pre.next # cur 指向反转区间的第一个节点它只负责“向后看” cur pre.next # 第 2 步头插法执行 right - left 次 for _ in range(right - left): nxt cur.next # 1. 先把 cur 后面的节点摘出来 cur.next nxt.next # 2. 让 cur 跨过 nxt直接连到 nxt 后面 nxt.next pre.next # 3. 让 nxt 指向 pre 后面的第一个节点 pre.next nxt # 4. 再把 nxt 接到 pre 的后面 return dummy.next逐行拆解一下这里的重点dummy节点的作用是统一处理left 1的情况不解释太多直接当固定套路记住。for _ in range(left - 1)让pre从dummy开始移动到第left - 1个节点。比如left 2pre移动 1 步正好指向节点 1。cur指向pre.next也就是left位置的那个节点。这个节点在整个过程中不向前移动每次循环只是把它后面的节点摘走。循环次数是right - left这很关键。比如区间长度是 3left2, right4只需要反转两次因为第一次把第 3 个节点挪到前面第二次把第 4 个节点挪到前面原本第 2 个节点自然就被挤到最后了。4.2 Java 版本对照实现/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { public ListNode reverseBetween(ListNode head, int left, int right) { ListNode dummy new ListNode(-1); dummy.next head; ListNode pre dummy; for (int i 0; i left - 1; i) { pre pre.next; } ListNode cur pre.next; for (int i 0; i right - left; i) { ListNode nxt cur.next; cur.next nxt.next; nxt.next pre.next; pre.next nxt; } return dummy.next; } }Java 版和 Python 版逻辑完全一致。面试时如果允许选语言我一般优先写 Python代码短、不容易写错但有些公司要求用 Java那也不慌逻辑是一样的只是语法换了皮。4.3 边界用例验证left1 和 right链表末尾这段一定要自己推一遍尤其是left 1时的执行过程。比如head [3,5], left 1, right 2初始化dummy - 3 - 5pre dummypre移动left - 1 0步所以pre仍然指向dummycur pre.next也就是节点 3循环right - left 1次nxt cur.next即节点 5cur.next nxt.next即节点 5 的 next为 None所以3.next Nonenxt.next pre.next即5.next 3pre.next nxt即dummy.next 5。最终链表是5 - 3返回dummy.next正确。再看right 链表末尾的情况比如head [1,2,3], left 1, right 3。此时效果等价于整个链表反转代码同样能正确处理。因为nxt每次摘取的都是cur.next当区间到达末尾时cur.next会变成 Nonenxt.next pre.next也照样执行不会产生空指针异常。5. 常见问题与排查技巧实录不管我写多少遍这道题总能在评论区看到几乎相同的几个问题。这里集中整理一下每个问题都是真实的踩坑经历。5.1 循环终止条件写错到底执行几次我看到的最常见错误就是把第二个 for 循环的次数写成right - left 1甚至right - left 2。记住反转区间left到right本质上只需要把区间内除了第一个节点以外的right - left个节点逐个提到最前面。比如 2 到 4除了第 2 个节点 2 本身还需要把节点 3 和节点 4 各提一次所以是 2 次也就是4 - 2 2。如果写成1第一次循环后链表就已经多处理了一个节点后面再循环下去就会把已经反转好的节点又挪动一次最终结果完全乱掉。5.2 指针更新顺序记不住先取 nxt再动 cur.next头插法四行代码里最核心也是最容易出错的一点是先保存nxt再修改nxt.next或cur.next。一旦你先改了cur.next你后面就找不到nxt了链表直接断掉。我用一句话记住这个顺序“先摘后接先记后改”。具体到代码里就是先记下nxt cur.next让cur跳过nxtcur.next nxt.next让nxt指向pre后面的节点把nxt挂在pre后面。第 3、4 步的顺序也不能颠倒。如果先执行pre.next nxt那pre.next就变成了nxt此时再执行nxt.next pre.next就让nxt.next指向了它自己形成环。这一步我至少看到五六个人在评论区问过为什么“链表变成环了”基本都是这个原因。5.3 易错点速查表易错点正确姿势left 1时没有虚拟头节点一律先建dummy返回dummy.next第二个循环写right-left1次严格写right-left次先改cur.next再取nxt先nxt cur.next再改指针nxt.next和pre.next的赋值顺序颠倒必须先nxt.next pre.next再pre.next nxt结束时cur有没有前进不需要cur位置不变变的是它后面连接的节点返回head还是dummy.next统一返回dummy.next防止头节点被换掉6. 从一道题刷穿一类题链表题的通用套路刷题最忌讳的就是一题一题地背答案而是要形成“题型意识”。92 题一旦吃透你会发现很多题目都是它的变体。6.1 与25题 K 个一组翻转链表的关联LeetCode 25 题要求每 K 个节点一组进行翻转。这个题本质上就是反复调用“区间反转”的能力。只需要把链表按 K 个一组划分对每一组执行区间反转然后处理好组与组之间的连接即可。如果 92 题你能裸写出来25 题你就只需要额外考虑两个点怎么确定一组的起始位置以及怎么把上一组的尾巴接到下一组的头上。反过来说如果 92 题还卡着25 题基本不会顺畅。另外LeetCode 24 题两两交换链表中的节点可以看成是 K2 的 25 题也是区间反转的一种特殊形态。6.2 面试中如何快速给出手写代码面试手写链表题我有一个固定的节奏先画图把pre、cur、nxt标出来确定循环步骤写dummy节点直接避开头节点变更问题写出定位pre的循环写出头插法的四行核心交换逻辑测两个边界用例left 1和right n最后再口头跟面试官确认一下时间复杂度和空间复杂度。这套流程走下来基本不会翻车。尤其是第 5 步很多人写出了代码就觉得万事大吉结果面试官随手改一个参数代码就崩了。养成“写完就测边界”的习惯能让你在面试里显得非常专业。6.3 扩展思考递归写法与原地算法92 题除了迭代写法也可以用递归实现区间反转。递归的核心思想是“递归到 right 位置后开始逐个返回并调整指针”代码很简洁但理解成本会高一些。我个人建议优先掌握迭代写法递归作为进阶内容面试时如果不问就不主动写。另外这道题完全可以纯原地完成不需要额外开辟数组或者其他数据结构。在 LeetCode 上这道题的官方题解和热门题解也都强调 O(1) 空间复杂度。遇到任何说“这个题必须用额外空间才能做”的说法都要打个问号。把 92 题刷透之后建议再花一天时间刷掉这几个关联题206 题反转整个链表、24 题两两交换节点、25 题K 个一组翻转。你会发现这些题之间有一个非常清晰的递进关系而 92 题正是整个链条里承上启下的关键一环。我个人在实际练习中的体会是链表题最考验的就是“指针修改顺序”的肌肉记忆。一道 92 题如果能在不看答案的情况下15 分钟内手写出来并一次性通过所有测试用例那么链表这一关你基本算是站稳了。别急着追求刷题数量先把这道题吃透后面的路会顺畅很多。
