尧图网站建设 
1. 题目解读第92题到底在考什么1.1 题目描述与核心需求LeetCode 92题“反转链表 II”是一道非常典型的链表操作题目在面试中出现频率很高。题目要求很简单给你单链表的头指针 head 和两个整数 left 和 right其中 left right请你反转从位置 left 到位置 right 的链表节点返回反转后的链表。举个例子链表是 1 - 2 - 3 - 4 - 5left 2right 4那么反转第2个节点到第4个节点后结果是 1 - 4 - 3 - 2 - 5。注意这里的位置是从1开始计数的不是从0开始这个细节第一次做的时候特别容易踩坑。看起来这题就是第206题“反转链表”的升级版只反转一部分而不是全部。但就是“一部分”这三个字让题目的复杂度上升了一个档次。因为你要先找到反转的起点和终点再执行反转然后还要把反转后的子链表和前后两段正确连接起来任何一个指针指向错了整个链表就断了。这道题的核心考点我总结下来有三个第一对单链表指针操作的基本功能不能在不引入额外数组的情况下原地反转第二边界情况的处理left 1、right 链表长度、left right 这些极端情况是否考虑清楚第三代码的简洁性和可读性面试官经常会要求你现场写这道题用什么样的思路决定了你的代码有多少bug。1.2 涉及的核心知识点官方标签里这道题属于“链表”和“双指针”但实际做题你会发现牵扯到的知识点远不止这些。我把涉及到的核心知识拆开来看单链表基本结构节点定义、next指针的指向关系这是所有链表题的基础。虚拟头节点dummy node这是处理链表头节点可能变化时最常用的技巧。因为反转后原链表的头节点可能变成别的节点但引入一个dummy节点做哨兵就可以避免对头节点的特殊判断。双指针定位要找到 left 位置的前一个节点和 right 位置的节点用双指针一次遍历就能搞定。局部反转的实现方式这里至少有三种写法头插法、指针交换法、递归法。每种写法的代码风格和效率都不一样但核心思想都是把某个区间内的节点之间的next指针方向反过来。复杂度分析时间复杂度和空间复杂度的计算尤其是递归解法的栈空间开销面试时经常被追问。有经验的读者可能发现了这道题其实是很多链表难题的“地基”。比如第25题“K个一组翻转链表”可以看成是多次调用“反转一个区间”的功能第24题“两两交换链表中的节点”可以看成是区间长度为2的特例。所以把92题吃透后面的进阶题都会轻松很多。2. 解法一迭代法头插法的完整拆解2.1 核心思路先把链表分成三部分我最初刷这道题的时候第一反应是把链表拆成三段左边不反转的部分、中间要反转的部分、右边不反转的部分。然后反转中间段再拼接回去。这个思路是对的但代码实现上有很多细节。更优雅、也更正统的做法是头插法。头插法的精髓在于遍历到要反转的区间时每次都把当前节点后面的那个节点“拔”出来插到区间起始位置的前面。这样一遍遍历下来区间的顺序就自然反过来了。我画个图帮大家理解一下。假设链表是dummy - 1 - 2 - 3 - 4 - 5left 2right 4。我们用一个 pre 指针指向 left 前一个节点即节点1。用一个 cur 指针指向 left 位置的节点即节点2。然后一步步来第一步cur指向2cur后面的节点是3。把3拔出来插到pre的后面。链表变成dummy - 1 - 3 - 2 - 4 - 5此时 cur 仍然指向2cur后面的节点变成了4。第二步把4拔出来插到pre的后面。链表变成dummy - 1 - 4 - 3 - 2 - 5循环执行 right - left 次区间内的节点顺序就完全反转了。最终结果是 1 - 4 - 3 - 2 - 5完全正确。这个思路的巧妙之处在于它根本不需要把子链表单独拆出来再拼接而是在遍历过程中原地完成了“拆、插、连”三个动作。理解这个逻辑之后代码就非常好写了。2.2 关键步骤与代码实现头插法的代码非常简洁我先把C版本贴出来然后逐行解释class Solution { public: ListNode* reverseBetween(ListNode* head, int left, int right) { ListNode* dummy new ListNode(0); dummy-next head; ListNode* pre dummy; // 1. 让 pre 指向 left 位置的前一个节点 for (int i 1; i left; i) { pre pre-next; } // 2. cur 指向 left 位置的节点 ListNode* cur pre-next; // 3. 头插法反转区间 for (int i left; i right; i) { ListNode* nxt cur-next; // 要移动的节点 cur-next nxt-next; // 把 cur 和 nxt 后面的节点连起来 nxt-next pre-next; // nxt 指向区间第一个节点 pre-next nxt; // pre 的 next 指向 nxt } return dummy-next; } };这段代码的核心就是第三步的那个循环一共执行 right - left 次每次做四行操作。我强烈建议读者把这个循环的四行操作背下来因为写熟练之后第25题“K个一组翻转链表”用的也是几乎一样的循环体。我再补充一个Python版本方便用Python刷题的朋友直接参考class Solution: def reverseBetween(self, head: Optional[ListNode], left: int, right: int) - Optional[ListNode]: 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这两段代码的时间复杂度都是 O(n)空间复杂度 O(1)。整个遍历只需要走一遍链表没有任何额外的存储开销是这道题的最优解法之一。2.3 为什么使用虚拟头节点边界条件深度分析很多初学者都会问为什么要加一个 dummy 节点如果不加会怎么样答案是不加的话当 left 1 时反转区间的第一个节点就是原链表的头节点反转后头节点会改变。如果没有 dummy 节点做哨兵你就得对“pre 为 nullptr”的情况做特殊处理代码会变得很啰嗦。举例来说如果链表是 1 - 2 - 3left 1right 3反转后变成 3 - 2 - 1。如果没有 dummy 节点你最终需要返回新的头节点 3但代码里没有统一的入口来拿到这个新头节点。而有了 dummy 节点不管头节点怎么变dummy-next 始终指向当前链表的头节点返回值一律是 dummy-next大大简化了逻辑。这里面还有几个边界条件值得单独拿出来说left right区间只有一个节点循环次数为0什么也不做直接返回原链表。代码天然支持这种情况不需要额外判断。left 1pre 就是 dummy头插法直接操作不会出现空指针问题。right 链表长度区间延伸到链表末尾cur 的 next 可能会变成 nullptr但代码中 cur-next nxt-next 这一句无论 nxt 是不是最后一个节点都能正常执行。最右边不反转部分为空不需要拼接。链表只有一个节点此时 left right 1循环不执行正确返回该节点。这四种情况在头插法的代码里都不需要单独写if判断这就是dummy节点带来的好处。我在面试中见过不少候选人虽然能写出反转逻辑但因为没有用dummy节点代码里到处是 if (pre nullptr) 的特判不仅丑还容易漏判。这个经验大家可以记一下。3. 解法二递归法思路与进阶应用3.1 递归核心先学会反转前N个节点除了迭代法递归法也是解这道题的一个经典路线。不过递归的思路相对跳跃我建议你把它拆成两步来学。第一步先解决一个简化版问题反转链表的前 n 个节点。这个问题的递归写法非常经典ListNode* successor nullptr; // 第 n1 个节点后续要用 // 反转以 head 为起点的前 n 个节点返回新的头节点 ListNode* reverseN(ListNode* head, int n) { if (n 1) { successor head-next; // 记录第 n1 个节点 return head; } ListNode* last reverseN(head-next, n - 1); head-next-next head; // 让下一个节点的 next 指向自己 head-next successor; // 自己指向第 n1 个节点 return last; }这个函数的执行过程是递归到第 n 个节点时把 successor 记录好然后逐层返回每层都把下一个节点的 next 指向自己再把自己的 next 指向 successor。最终得到的链表前 n 个节点完全反转而且第 n 个节点的 next 正确指向了原来的第 n1 个节点链表不会断。这里最反直觉的一点是为什么 head-next successor 而不是 head-next nullptr因为反转前 n 个节点后新的第 n 个节点也就是原来的第一个节点必须指向第 n1 个节点才能保证链表完整否则后半段就丢了。我第一次写递归的时候就是忘了这一句结果反转后的链表后面什么都不剩了调试了很久才发现问题。3.2 从递归到解出第92题有了 reverseN 这个基础函数第92题就可以很优雅地转化了。核心逻辑是如果 left 1那问题就直接变成“反转前 right 个节点”调用 reverseN(head, right) 即可。如果 left 1我们可以把 head 往后移动同时把 left 和 right 都减1直到 left 1 为止。也就是说head 后面的那个子链表里要反转的区间变成了 [left - 1, right - 1]。翻译成代码就是ListNode* reverseBetween(ListNode* head, int left, int right) { if (left 1) { return reverseN(head, right); } head-next reverseBetween(head-next, left - 1, right - 1); return head; }这个写法非常简洁但要注意递归时 left 和 right 一起减1而不是只减 left。原因在于右边界是相对于当前子链表头节点的位置head 每往后走一位左边界和右边界都往前挪一位。如果只减 left那么 right 表示的绝对位置就错了。递归法的时间复杂度同样是 O(n)但空间复杂度是 O(n)因为递归深度最坏情况下等于链表长度 n需要消耗 n 层的函数调用栈。这在链表很长的时候可能会栈溢出所以实际工程中更推荐迭代法。但递归法的代码非常短逻辑也很巧妙面试时如果你能在迭代法的基础上再补充一段递归法思路会显得你对链表的理解更深一层。我个人的建议是平时练习时迭代法和递归法都要多写几遍因为这两种思路在后续的二叉树、图遍历等问题中会反复出现。尤其你对递归的掌握不够的时候把这道题吃透是特别好的训练素材。4. 链表题型的横向对比与刷题路线4.1 反转类题目的进阶层级单链表反转这个题型在LeetCode上其实有一条非常清晰的进阶路线。我按照难度从低到高给你整理一下题号题目名称核心考点与92题的关系206反转链表整条链表反转92题的特例left1right链表长度92反转链表 II区间反转核心题型掌握头插法24两两交换链表中的节点每两个节点反转区间长度为2的92题25K个一组翻转链表每K个节点反转需要分治多次调用92题的逻辑从表中可以看到206题是基础中的基础必须做到秒杀。92题是在206的基础上增加了区间定位中间还牵扯到子链表与前后段的拼接。24题虽然是“交换”但本质上是反转长度为2的区间理解了92题的头插法后24题几乎没有新知识点。25题则是在92题的基础上把“反转一个区间”这件事循环做了很多次同时每处理完一组还要更新 pre 的指向。我建议刷题顺序是 206 - 92 - 24 - 25。这条路线是我自己验证过的每一步都踩在前一步的知识点上不会出现知识点跳级导致卡壳的情况。4.2 周赛中的链表高频考点从最近几场周赛的题目来看链表题目很少单独考一个反转就完了通常会和下面几个知识点组合出现链表 数学比如用链表表示的大整数相加、相乘需要先反转链表再逐位运算。周赛里经常出现这种题核心思路就是把链表反转成方便计算的顺序算完再反转回去。链表 双指针比如寻找链表的中间节点、判断是否有环、寻找环的入口这些题虽然不直接考反转但在别的综合题里经常作为前置步骤出现。像是链表的归并排序就要先找中点拆分链表。链表 栈/递归比如判断回文链表直接把后半段反转然后和前半段逐一比较。这类题用栈也能做但空间复杂度是 O(n)改成反转后半段就能做到 O(1) 空间。这里特别提一个热词“leetcode旅行商”虽然跟链表反转不太沾边但反映了在部分热门题解中人们会把链表的指针跳转和状态空间搜索结合起来。我见过有人用链表结构去模拟路径选择把每个节点的 next 当成路径分支再通过反转或重连来优化路径思路很新颖但对大多数刷题场景来说还是先把基础链表操作吃透更重要。4.3 面试中关于时间与空间复杂度的追问链表题在面试中的追问率很高几乎必问的题目就是“你这个方法的时间复杂度和空间复杂度是多少能不能优化到 O(1) 空间”很多候选人能答出迭代法是 O(n) 时间和 O(1) 空间但一旦用了递归被问到空间复杂度就答不上来。需要注意递归的空间复杂度是 O(n)因为每一层递归都要消耗栈空间。这个区别在 92 题上体现得很典型迭代法空间 O(1)递归法空间 O(n)功能完全一样。当面试官进一步追问“为什么迭代法是 O(1) 空间”时你要能说清楚因为整个算法只用了固定数量的指针变量比如 pre、cur、nxt不论链表有多长额外变量数不变。而递归每深入一层就要为局部变量和返回地址开辟新的栈帧所以空间和链表长度成正比。还有一个容易被追问的点是“如果链表有环你的代码会不会死循环”。这其实是个陷阱题因为本题的输入默认是无环单链表但如果面试官这样问你要回答有环的情况下理论上反转操作会让环结构被破坏代码可能陷入无限循环所以需要在开始操作前检查环的存在。这就是为什么很多链表综合题里会先做一个“判断是否有环”的前置步骤。5. 常见问题与实操调试技巧5.1 边界条件处理的N个陷阱我在刷这道题以及给同事做 code review 的过程中总结了几个高频翻车场景每一个都是真实踩过的坑陷阱一位置从1开始还是从0开始。题目明确说了位置从1开始但很多人习惯了数组下标从0开始写循环的时候就容易多走一步或者少走一步。我建议在代码里把定位 pre 的循环写成 for (int i 1; i left; i)这个写法最直观不容易出错。陷阱二头插法的循环次数。循环体执行的是“把 cur 后面的节点插到最前面”区间内有 right - left 1 个节点需要移动 right - left 次。如果你写成 i right那就会多移动一次把区间外的一个节点也卷进来了导致结果完全错乱。陷阱三忘记更新 cur 的 next 为区间外节点。头插法里每一次循环都会执行 cur-next nxt-next这句话保证了 cur 始终指向区间内尚未反转的部分。如果哪一次循环里漏掉了这一句链表就会在某次插完后断开。我在本地调试时就是用这一句写没写来快速定位 bug 的。陷阱四递归法里 left 和 right 没有一起减。前面说过递归进入子链表时左边界和右边界必须同时减1。如果只减 left最终的 right 会大于子链表长度导致 reverseN 递归到空指针直接崩掉。我把这些问题整理成一个速查表方便大家刷题时对照陷阱场景错误表现正确做法位置循环次数错误反转区间偏了一位pre 移动 left-1 次头插法循环多一次区间外节点被反转循环 right-left 次递归只减 left子链表超长空指针left 和 right 同时减1忘记连接后继节点反转后半段丢失手动给新链表尾部接上 successor不用 dummy 节点left1 时逻辑分支爆炸始终用 dummy 统一返回入口5.2 链表可视化调试新手最需要掌握的技巧链表题相比数组题调试难度更大因为你看不到指针之间的连接关系。数组打印出来一目了然链表打印出来就只有一堆地址然后 head-next 指向哪里全靠脑补。所以我会花一点篇幅讲一下链表调试的经验。最常见的做法是写一个打印链表的辅助函数void printList(ListNode* head) { while (head ! nullptr) { cout head-val - ; head head-next; } cout nullptr endl; }然后在你怀疑出错的位置前后都调用一下这个函数。比如在头插法循环内部每执行完一次插入就打印一次整个链表。这样你可以直观地看到每次“拔出来再插到最前面”之后链表变成了什么样出问题时一眼就能看出是哪个指针接错了。对于递归法可以打印递归函数的入口参数和返回结果。比如 reverseN 函数进来的 head-val 是多少返回的 last 是多少这样能帮你理清递归的调用顺序。我刷题那会儿特别喜欢在递归入口打一行日志等代码稳定后再删掉效率非常高。如果不想自己打日志也可以用LeetCode官方自带的调试工具在Run代码时勾选“自定义测试用例”一步步看链表的节点值变化。对于只看最终结果的简单检查这个工具够用但对于复杂的反转过程还是打日志更可靠。5.3 一道题掌握链表操作的通用模板最后分享一个我自己的做法把92题作为链表操作的“万能模板题”把它涉及到的代码片段抽出来复用。第一个片段是定位移动 pre 指针到目标区间前一个节点。这几乎是所有“区间操作”类型题目的共同前缀ListNode* pre dummy; for (int i 1; i left; i) { pre pre-next; }第二个片段是头插把 cur 后面的节点移动到 pre 的后面。这个片段可以复用到 24、25 题中ListNode* cur pre-next; for (...) { ListNode* nxt cur-next; cur-next nxt-next; nxt-next pre-next; pre-next nxt; }这两个片段组合起来再配合 dummy 节点基本覆盖了 LeetCode 上 80% 的单链表指针操作类题目。你会发现 92 题练熟之后再去做 24、25 题代码几乎不用太多修改只是循环条件和外层控制结构变了一下。如果你刷题的时候总是卡在链表的指针操作上建议不要急着刷更多新题而是把 206、92、24、25 这四道题反复写写到不需要思考能手写出来的程度链表的操作手感自然就有了。我身边有不少朋友用这个方法把链表这个分类从“看到就头疼”练到“白板默写全对”非常管用。我个人刷题的真实感受是92题是最容易被低估的一道题。它表面上是206题的简单升级但如果你深入琢磨就会发现它把链表的定位、反转、拼接、边界处理全部串起来了。很多在更复杂链表题目里遇到的问题都能在92题里找到影子。把这题吃透后面遇到20多道链表相关的衍生题你都会觉得思路特别顺。 LeetCode 92 反转链表 II 详解：头插法、递归与边界处理
1. 题目解读第92题到底在考什么1.1 题目描述与核心需求LeetCode 92题“反转链表 II”是一道非常典型的链表操作题目在面试中出现频率很高。题目要求很简单给你单链表的头指针 head 和两个整数 left 和 right其中 left right请你反转从位置 left 到位置 right 的链表节点返回反转后的链表。举个例子链表是 1 - 2 - 3 - 4 - 5left 2right 4那么反转第2个节点到第4个节点后结果是 1 - 4 - 3 - 2 - 5。注意这里的位置是从1开始计数的不是从0开始这个细节第一次做的时候特别容易踩坑。看起来这题就是第206题“反转链表”的升级版只反转一部分而不是全部。但就是“一部分”这三个字让题目的复杂度上升了一个档次。因为你要先找到反转的起点和终点再执行反转然后还要把反转后的子链表和前后两段正确连接起来任何一个指针指向错了整个链表就断了。这道题的核心考点我总结下来有三个第一对单链表指针操作的基本功能不能在不引入额外数组的情况下原地反转第二边界情况的处理left 1、right 链表长度、left right 这些极端情况是否考虑清楚第三代码的简洁性和可读性面试官经常会要求你现场写这道题用什么样的思路决定了你的代码有多少bug。1.2 涉及的核心知识点官方标签里这道题属于“链表”和“双指针”但实际做题你会发现牵扯到的知识点远不止这些。我把涉及到的核心知识拆开来看单链表基本结构节点定义、next指针的指向关系这是所有链表题的基础。虚拟头节点dummy node这是处理链表头节点可能变化时最常用的技巧。因为反转后原链表的头节点可能变成别的节点但引入一个dummy节点做哨兵就可以避免对头节点的特殊判断。双指针定位要找到 left 位置的前一个节点和 right 位置的节点用双指针一次遍历就能搞定。局部反转的实现方式这里至少有三种写法头插法、指针交换法、递归法。每种写法的代码风格和效率都不一样但核心思想都是把某个区间内的节点之间的next指针方向反过来。复杂度分析时间复杂度和空间复杂度的计算尤其是递归解法的栈空间开销面试时经常被追问。有经验的读者可能发现了这道题其实是很多链表难题的“地基”。比如第25题“K个一组翻转链表”可以看成是多次调用“反转一个区间”的功能第24题“两两交换链表中的节点”可以看成是区间长度为2的特例。所以把92题吃透后面的进阶题都会轻松很多。2. 解法一迭代法头插法的完整拆解2.1 核心思路先把链表分成三部分我最初刷这道题的时候第一反应是把链表拆成三段左边不反转的部分、中间要反转的部分、右边不反转的部分。然后反转中间段再拼接回去。这个思路是对的但代码实现上有很多细节。更优雅、也更正统的做法是头插法。头插法的精髓在于遍历到要反转的区间时每次都把当前节点后面的那个节点“拔”出来插到区间起始位置的前面。这样一遍遍历下来区间的顺序就自然反过来了。我画个图帮大家理解一下。假设链表是dummy - 1 - 2 - 3 - 4 - 5left 2right 4。我们用一个 pre 指针指向 left 前一个节点即节点1。用一个 cur 指针指向 left 位置的节点即节点2。然后一步步来第一步cur指向2cur后面的节点是3。把3拔出来插到pre的后面。链表变成dummy - 1 - 3 - 2 - 4 - 5此时 cur 仍然指向2cur后面的节点变成了4。第二步把4拔出来插到pre的后面。链表变成dummy - 1 - 4 - 3 - 2 - 5循环执行 right - left 次区间内的节点顺序就完全反转了。最终结果是 1 - 4 - 3 - 2 - 5完全正确。这个思路的巧妙之处在于它根本不需要把子链表单独拆出来再拼接而是在遍历过程中原地完成了“拆、插、连”三个动作。理解这个逻辑之后代码就非常好写了。2.2 关键步骤与代码实现头插法的代码非常简洁我先把C版本贴出来然后逐行解释class Solution { public: ListNode* reverseBetween(ListNode* head, int left, int right) { ListNode* dummy new ListNode(0); dummy-next head; ListNode* pre dummy; // 1. 让 pre 指向 left 位置的前一个节点 for (int i 1; i left; i) { pre pre-next; } // 2. cur 指向 left 位置的节点 ListNode* cur pre-next; // 3. 头插法反转区间 for (int i left; i right; i) { ListNode* nxt cur-next; // 要移动的节点 cur-next nxt-next; // 把 cur 和 nxt 后面的节点连起来 nxt-next pre-next; // nxt 指向区间第一个节点 pre-next nxt; // pre 的 next 指向 nxt } return dummy-next; } };这段代码的核心就是第三步的那个循环一共执行 right - left 次每次做四行操作。我强烈建议读者把这个循环的四行操作背下来因为写熟练之后第25题“K个一组翻转链表”用的也是几乎一样的循环体。我再补充一个Python版本方便用Python刷题的朋友直接参考class Solution: def reverseBetween(self, head: Optional[ListNode], left: int, right: int) - Optional[ListNode]: 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这两段代码的时间复杂度都是 O(n)空间复杂度 O(1)。整个遍历只需要走一遍链表没有任何额外的存储开销是这道题的最优解法之一。2.3 为什么使用虚拟头节点边界条件深度分析很多初学者都会问为什么要加一个 dummy 节点如果不加会怎么样答案是不加的话当 left 1 时反转区间的第一个节点就是原链表的头节点反转后头节点会改变。如果没有 dummy 节点做哨兵你就得对“pre 为 nullptr”的情况做特殊处理代码会变得很啰嗦。举例来说如果链表是 1 - 2 - 3left 1right 3反转后变成 3 - 2 - 1。如果没有 dummy 节点你最终需要返回新的头节点 3但代码里没有统一的入口来拿到这个新头节点。而有了 dummy 节点不管头节点怎么变dummy-next 始终指向当前链表的头节点返回值一律是 dummy-next大大简化了逻辑。这里面还有几个边界条件值得单独拿出来说left right区间只有一个节点循环次数为0什么也不做直接返回原链表。代码天然支持这种情况不需要额外判断。left 1pre 就是 dummy头插法直接操作不会出现空指针问题。right 链表长度区间延伸到链表末尾cur 的 next 可能会变成 nullptr但代码中 cur-next nxt-next 这一句无论 nxt 是不是最后一个节点都能正常执行。最右边不反转部分为空不需要拼接。链表只有一个节点此时 left right 1循环不执行正确返回该节点。这四种情况在头插法的代码里都不需要单独写if判断这就是dummy节点带来的好处。我在面试中见过不少候选人虽然能写出反转逻辑但因为没有用dummy节点代码里到处是 if (pre nullptr) 的特判不仅丑还容易漏判。这个经验大家可以记一下。3. 解法二递归法思路与进阶应用3.1 递归核心先学会反转前N个节点除了迭代法递归法也是解这道题的一个经典路线。不过递归的思路相对跳跃我建议你把它拆成两步来学。第一步先解决一个简化版问题反转链表的前 n 个节点。这个问题的递归写法非常经典ListNode* successor nullptr; // 第 n1 个节点后续要用 // 反转以 head 为起点的前 n 个节点返回新的头节点 ListNode* reverseN(ListNode* head, int n) { if (n 1) { successor head-next; // 记录第 n1 个节点 return head; } ListNode* last reverseN(head-next, n - 1); head-next-next head; // 让下一个节点的 next 指向自己 head-next successor; // 自己指向第 n1 个节点 return last; }这个函数的执行过程是递归到第 n 个节点时把 successor 记录好然后逐层返回每层都把下一个节点的 next 指向自己再把自己的 next 指向 successor。最终得到的链表前 n 个节点完全反转而且第 n 个节点的 next 正确指向了原来的第 n1 个节点链表不会断。这里最反直觉的一点是为什么 head-next successor 而不是 head-next nullptr因为反转前 n 个节点后新的第 n 个节点也就是原来的第一个节点必须指向第 n1 个节点才能保证链表完整否则后半段就丢了。我第一次写递归的时候就是忘了这一句结果反转后的链表后面什么都不剩了调试了很久才发现问题。3.2 从递归到解出第92题有了 reverseN 这个基础函数第92题就可以很优雅地转化了。核心逻辑是如果 left 1那问题就直接变成“反转前 right 个节点”调用 reverseN(head, right) 即可。如果 left 1我们可以把 head 往后移动同时把 left 和 right 都减1直到 left 1 为止。也就是说head 后面的那个子链表里要反转的区间变成了 [left - 1, right - 1]。翻译成代码就是ListNode* reverseBetween(ListNode* head, int left, int right) { if (left 1) { return reverseN(head, right); } head-next reverseBetween(head-next, left - 1, right - 1); return head; }这个写法非常简洁但要注意递归时 left 和 right 一起减1而不是只减 left。原因在于右边界是相对于当前子链表头节点的位置head 每往后走一位左边界和右边界都往前挪一位。如果只减 left那么 right 表示的绝对位置就错了。递归法的时间复杂度同样是 O(n)但空间复杂度是 O(n)因为递归深度最坏情况下等于链表长度 n需要消耗 n 层的函数调用栈。这在链表很长的时候可能会栈溢出所以实际工程中更推荐迭代法。但递归法的代码非常短逻辑也很巧妙面试时如果你能在迭代法的基础上再补充一段递归法思路会显得你对链表的理解更深一层。我个人的建议是平时练习时迭代法和递归法都要多写几遍因为这两种思路在后续的二叉树、图遍历等问题中会反复出现。尤其你对递归的掌握不够的时候把这道题吃透是特别好的训练素材。4. 链表题型的横向对比与刷题路线4.1 反转类题目的进阶层级单链表反转这个题型在LeetCode上其实有一条非常清晰的进阶路线。我按照难度从低到高给你整理一下题号题目名称核心考点与92题的关系206反转链表整条链表反转92题的特例left1right链表长度92反转链表 II区间反转核心题型掌握头插法24两两交换链表中的节点每两个节点反转区间长度为2的92题25K个一组翻转链表每K个节点反转需要分治多次调用92题的逻辑从表中可以看到206题是基础中的基础必须做到秒杀。92题是在206的基础上增加了区间定位中间还牵扯到子链表与前后段的拼接。24题虽然是“交换”但本质上是反转长度为2的区间理解了92题的头插法后24题几乎没有新知识点。25题则是在92题的基础上把“反转一个区间”这件事循环做了很多次同时每处理完一组还要更新 pre 的指向。我建议刷题顺序是 206 - 92 - 24 - 25。这条路线是我自己验证过的每一步都踩在前一步的知识点上不会出现知识点跳级导致卡壳的情况。4.2 周赛中的链表高频考点从最近几场周赛的题目来看链表题目很少单独考一个反转就完了通常会和下面几个知识点组合出现链表 数学比如用链表表示的大整数相加、相乘需要先反转链表再逐位运算。周赛里经常出现这种题核心思路就是把链表反转成方便计算的顺序算完再反转回去。链表 双指针比如寻找链表的中间节点、判断是否有环、寻找环的入口这些题虽然不直接考反转但在别的综合题里经常作为前置步骤出现。像是链表的归并排序就要先找中点拆分链表。链表 栈/递归比如判断回文链表直接把后半段反转然后和前半段逐一比较。这类题用栈也能做但空间复杂度是 O(n)改成反转后半段就能做到 O(1) 空间。这里特别提一个热词“leetcode旅行商”虽然跟链表反转不太沾边但反映了在部分热门题解中人们会把链表的指针跳转和状态空间搜索结合起来。我见过有人用链表结构去模拟路径选择把每个节点的 next 当成路径分支再通过反转或重连来优化路径思路很新颖但对大多数刷题场景来说还是先把基础链表操作吃透更重要。4.3 面试中关于时间与空间复杂度的追问链表题在面试中的追问率很高几乎必问的题目就是“你这个方法的时间复杂度和空间复杂度是多少能不能优化到 O(1) 空间”很多候选人能答出迭代法是 O(n) 时间和 O(1) 空间但一旦用了递归被问到空间复杂度就答不上来。需要注意递归的空间复杂度是 O(n)因为每一层递归都要消耗栈空间。这个区别在 92 题上体现得很典型迭代法空间 O(1)递归法空间 O(n)功能完全一样。当面试官进一步追问“为什么迭代法是 O(1) 空间”时你要能说清楚因为整个算法只用了固定数量的指针变量比如 pre、cur、nxt不论链表有多长额外变量数不变。而递归每深入一层就要为局部变量和返回地址开辟新的栈帧所以空间和链表长度成正比。还有一个容易被追问的点是“如果链表有环你的代码会不会死循环”。这其实是个陷阱题因为本题的输入默认是无环单链表但如果面试官这样问你要回答有环的情况下理论上反转操作会让环结构被破坏代码可能陷入无限循环所以需要在开始操作前检查环的存在。这就是为什么很多链表综合题里会先做一个“判断是否有环”的前置步骤。5. 常见问题与实操调试技巧5.1 边界条件处理的N个陷阱我在刷这道题以及给同事做 code review 的过程中总结了几个高频翻车场景每一个都是真实踩过的坑陷阱一位置从1开始还是从0开始。题目明确说了位置从1开始但很多人习惯了数组下标从0开始写循环的时候就容易多走一步或者少走一步。我建议在代码里把定位 pre 的循环写成 for (int i 1; i left; i)这个写法最直观不容易出错。陷阱二头插法的循环次数。循环体执行的是“把 cur 后面的节点插到最前面”区间内有 right - left 1 个节点需要移动 right - left 次。如果你写成 i right那就会多移动一次把区间外的一个节点也卷进来了导致结果完全错乱。陷阱三忘记更新 cur 的 next 为区间外节点。头插法里每一次循环都会执行 cur-next nxt-next这句话保证了 cur 始终指向区间内尚未反转的部分。如果哪一次循环里漏掉了这一句链表就会在某次插完后断开。我在本地调试时就是用这一句写没写来快速定位 bug 的。陷阱四递归法里 left 和 right 没有一起减。前面说过递归进入子链表时左边界和右边界必须同时减1。如果只减 left最终的 right 会大于子链表长度导致 reverseN 递归到空指针直接崩掉。我把这些问题整理成一个速查表方便大家刷题时对照陷阱场景错误表现正确做法位置循环次数错误反转区间偏了一位pre 移动 left-1 次头插法循环多一次区间外节点被反转循环 right-left 次递归只减 left子链表超长空指针left 和 right 同时减1忘记连接后继节点反转后半段丢失手动给新链表尾部接上 successor不用 dummy 节点left1 时逻辑分支爆炸始终用 dummy 统一返回入口5.2 链表可视化调试新手最需要掌握的技巧链表题相比数组题调试难度更大因为你看不到指针之间的连接关系。数组打印出来一目了然链表打印出来就只有一堆地址然后 head-next 指向哪里全靠脑补。所以我会花一点篇幅讲一下链表调试的经验。最常见的做法是写一个打印链表的辅助函数void printList(ListNode* head) { while (head ! nullptr) { cout head-val - ; head head-next; } cout nullptr endl; }然后在你怀疑出错的位置前后都调用一下这个函数。比如在头插法循环内部每执行完一次插入就打印一次整个链表。这样你可以直观地看到每次“拔出来再插到最前面”之后链表变成了什么样出问题时一眼就能看出是哪个指针接错了。对于递归法可以打印递归函数的入口参数和返回结果。比如 reverseN 函数进来的 head-val 是多少返回的 last 是多少这样能帮你理清递归的调用顺序。我刷题那会儿特别喜欢在递归入口打一行日志等代码稳定后再删掉效率非常高。如果不想自己打日志也可以用LeetCode官方自带的调试工具在Run代码时勾选“自定义测试用例”一步步看链表的节点值变化。对于只看最终结果的简单检查这个工具够用但对于复杂的反转过程还是打日志更可靠。5.3 一道题掌握链表操作的通用模板最后分享一个我自己的做法把92题作为链表操作的“万能模板题”把它涉及到的代码片段抽出来复用。第一个片段是定位移动 pre 指针到目标区间前一个节点。这几乎是所有“区间操作”类型题目的共同前缀ListNode* pre dummy; for (int i 1; i left; i) { pre pre-next; }第二个片段是头插把 cur 后面的节点移动到 pre 的后面。这个片段可以复用到 24、25 题中ListNode* cur pre-next; for (...) { ListNode* nxt cur-next; cur-next nxt-next; nxt-next pre-next; pre-next nxt; }这两个片段组合起来再配合 dummy 节点基本覆盖了 LeetCode 上 80% 的单链表指针操作类题目。你会发现 92 题练熟之后再去做 24、25 题代码几乎不用太多修改只是循环条件和外层控制结构变了一下。如果你刷题的时候总是卡在链表的指针操作上建议不要急着刷更多新题而是把 206、92、24、25 这四道题反复写写到不需要思考能手写出来的程度链表的操作手感自然就有了。我身边有不少朋友用这个方法把链表这个分类从“看到就头疼”练到“白板默写全对”非常管用。我个人刷题的真实感受是92题是最容易被低估的一道题。它表面上是206题的简单升级但如果你深入琢磨就会发现它把链表的定位、反转、拼接、边界处理全部串起来了。很多在更复杂链表题目里遇到的问题都能在92题里找到影子。把这题吃透后面遇到20多道链表相关的衍生题你都会觉得思路特别顺。