我在面试候选人的时候只要时间允许总会挑一道 LeetCode 92。这道区间反转题题目很短给定链表头节点和两个位置 left、right把中间这一段翻转后再拼回去。听上去只是反转整条链表的小改动可实际上它把哨兵技巧和递归反转的基本功全考了一遍。很多刷题一段时间的人206 反转整条链表能默写到了 92 却容易卡住——区别不在于会不会反转而在于会不会处理边界和拼接。今天我就把这道题的迭代、递归两套标准解法完整拆开讲讲每一步为什么这么写以及我在刷题和面试里反复踩过的坑。1. 题目拆解区间反转到底比整链反转难在哪1.1 先还原题目本来的样子LeetCode 92 的题干翻译过来非常简单给你单链表的头节点 head再给两个整数 left 和 right把从 left 到 right 这个闭区间内的节点反转其余节点保持原顺序最后返回新链表的头节点。举个例子链表是 1-2-3-4-5left2right4反转之后应该是 1-4-3-2-5。中间 2、3、4 三个节点掉了个头前后两段不动。很多第一次写这题的人会想这不就是 206 反转链表改个区间吗我先找到第 left 个节点然后反转 right-left1 个节点再接回去。思路确实没错但一旦落到代码上问题全出在“定位、反转、拼接”这三步的边界处理里。如果只背过整链反转的模板ListNode* pre nullptr; ListNode* cur head; while (cur) { ListNode* nxt cur-next; cur-next pre; pre cur; cur nxt; } return pre;这个模板默认从 head 一直反转到结尾最后原来的头节点会变成尾节点。但区间反转后面还拖着一截不需要反转的尾巴你直接套模板要么把尾巴也一起反转掉要么反转完发现链表接不回去。这道题真正想训练的不是“会不会反转指针”而是“在一个不可回退的线性结构上怎么精确地切出一段来局部重组”。1.2 单链表结构决定了这三件事必须做链表的节点通常是这样定义的struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} };这种结构是典型的不带头结点的单链表只有数据域和 next 指针。它的特点就是只能从某个节点往后遍历不能回头。所以任何区间操作都必须先明确三个位置。第一反转段的前驱节点是谁也就是第 left-1 个节点。第二反转段自己的起点是谁也就是第 left 个节点。第三反转段后面的后继节点是谁也就是第 right1 个节点。这三个位置对应到代码里就是三件必须做的事遍历定位、指针翻转、重新拼接。很多教材里的“单链表的基本操作实验”比如在指定位置插入节点、删除节点本质上做的也是同样的三件事。区别只是 LeetCode 92 把“插入”变成了“反转一整段再插回去”对指针操作的精度要求更高了。理解这一点之后你会意识到链表题从来不是考记忆力而是考你脑子里有没有这张“节点和指针变化图”。1.3 动手前先列的三个边界用例我在写任何链表题之前都会先在草稿纸上列三个边界用例LeetCode 92 尤其需要反转段包含头节点也就是 left1。这种情况下返回的头节点不再是原来的 head而是反转段的新头。区间长度只有 1也就是 leftright。链表实际不需要任何变化直接返回原 head。right 正好是链表末尾。反转段的“后段”为空处理时 next 指针可能会变成 nullptr恰恰是这种情况最容易把代码写乱。这三个边界如果不提前想清楚很容易写完代码靠提交去试错。我见过不少同学在 left1 的时候纠结半天最后用一堆 if 分支把代码搞得很丑。实际上后面讲到的哨兵节点就是专门用来消除这类分支的。2. 哨兵节点用 dummy 把“头可能会变”这个麻烦统一掉2.1 带头结点链表和不带头结点链表的陈年区别数据结构教材里单链表有两种常见写法不带头结点的链表头指针 head 直接指向第一个数据节点空链表时 head 为 nullptr带头结点的链表则额外有一个不存数据的头结点它的 next 才指向真正的数据节点。这两种写法对插入删除的影响非常大。不带头结点的链表如果要在头部插入或删除节点必须修改外部持有的头指针否则链表入口就丢了。带头结点的链表因为入口永远指向那个固定头结点不管你怎么操作数据节点外部的头指针都不用改。LeetCode 的题目默认是不带头结点的链表head 本身就是第一个数据节点。题目要求你返回反转后的新头其实是在暗示头节点有可能会变你得自己把这个入口接住。这时候就需要我们自己造一个“虚拟头结点”也就是刷题圈常说的 dummy 节点。2.2 dummy 在这里到底帮了什么忙区间反转的迭代解法里第一步永远是构造哨兵节点ListNode dummy(0); dummy.next head; ListNode* pre dummy;这个 dummy 不参与业务数据它的唯一使命是让整个链表的“入口”保持不变。不管 left 是 1 还是中间某个位置我们都可以从 dummy 出发通过移动 pre 找到第 left-1 个节点。最后返回 dummy.next就一定是反转后的真实头节点。为什么说这个技巧好用因为当 left1 时反转后的链表头会变成原来的第 right 个节点如果代码里从头就拿着 head 做操作最后很容易返回错。而 dummy 把所有情况都统一成了“pre 是反转段前驱节点”的形式空链表、单节点、头节点被替换这些特殊情况全部被吸收掉了。这跟带头结点链表里的头结点是同一个思路用一个不存数据的节点把边界情况转化成普通情况。刷题的时候自己不会给你加这个节点所以需要你手动建。2.3 判断什么时候该加哨兵的经验法则我总结了一个很简单的判断标准如果头节点在操作过程中可能被替换、删除或移动就优先考虑 dummy如果头节点一定不会变就不必加。LeetCode 92 是典型需要 dummy 的题目因为 left1 时头节点一定会被反转段的新头顶替。而 LeetCode 206 反转整条链表也可以加 dummy但完全没有必要——整条反转的最终头节点是原链表的最后一个节点直接用三指针法返回 pre 更干净。dummy 节点的另一个细节是它本身占用一个 ListNode 对象。虽然在线判题系统不在乎这点内存但如果你要跟面试官强调“迭代解法空间复杂度 O(1)”要主动指出这里的常数级额外空间包括 dummy 节点。还有最后一定是 return dummy.next不是 return dummy 或者 return head这是新手最容易犯的低级错误。3. 迭代解法把反转段逐个摘下来再插到 pre 后面3.1 三段式处理定位、摘取、重挂迭代解法的核心思路是把链表分成三段前段、反转段、后段。前段是不需要动的部分最后一个节点就是 pre反转段是要重新排序的部分后段是反转段原本后面的节点等反转完成后接回来。实际操作时我习惯用“头插法”来处理反转段。所谓头插法就是不断把当前节点从原位置摘下来插到 pre 的后面。因为每插一个新节点到 pre 后面之前插进去的节点就会往后退一个位置所以最后得到的顺序正好是原始区间顺序的逆序。这比传统的“三个指针依次翻转 next”更直观。传统三指针法适合反转整条链表因为整条链表反转后不需要考虑“后面的尾巴”。区间反转如果也用那种方法你还得额外记录反转段前后的节点再手动拼接反而更容易乱。头插法天然把拼接步骤简化了pre 永远站在反转段头部的门口每摘一个节点就往门口一放。3.2 完整走一遍 left2、right4 的例子我们还是用前面那个例子head 1-2-3-4-5left2right4。第一步建立 dummy 和 predummy - 1 - 2 - 3 - 4 - 5 pre dummy?注意 pre 要移动 left-1 次也就是从 dummy 走一步落到节点 1。cur 等于 pre-next也就是节点 2。dummy - 1 - 2 - 3 - 4 - 5 pre cur第一轮循环处理节点 3nxt cur-next // nxt 是 3 cur-next nxt-next; // 2 的 next 变成 4 nxt-next pre-next; // 3 的 next 变成 2 pre-next nxt; // 1 的 next 变成 3链表变成dummy - 1 - 3 - 2 - 4 - 5 pre cur处理完第一轮cur 还是节点 2nxt 已经被摘走。第二轮循环处理节点 4nxt cur-next; // nxt 是 4 cur-next nxt-next; // 2 的 next 变成 5 nxt-next pre-next; // 4 的 next 变成 3 pre-next nxt; // 1 的 next 变成 4链表变成dummy - 1 - 4 - 3 - 2 - 5循环结束返回 dummy.next得到 1-4-3-2-5。看到没有整个过程中 pre 和 cur 一直没变过变的是 pre 后面不断被插入新的节点。这样写代码心智负担小很多。3.3 迭代代码C 与 PythonC 版本class Solution { public: ListNode* reverseBetween(ListNode* head, int left, int right) { ListNode dummy(0, 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; } };Python 版本class Solution: def reverseBetween(self, head: ListNode, left: int, right: int) - 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两段代码几乎完全对应核心就是那三行指针操作。如果你用的 Python 是较新的 LeetCode 环境ListNode 定义里可能需要Optional[ListNode]但刷题时大多数情况直接用ListNode也能跑。3.4 刷这道题最常见的四个翻车点第一pre 的初始位置错了。pre 应该从 dummy 开始移动 left-1 步不是 left 步。如果你移动了 left 步pre 会落在第 left 个节点上也就是反转段的起点那插入位置就完全不对了。第二循环次数写成 right-left1。多转一轮的后果是会把区间后面的第一个节点也摘进反转段导致结果不对。循环次数是 right-left因为第一个节点不需要动从第二个开始每轮处理一个节点。第三忘记保存 nxt。在 cur-next 被修改前如果不先定住下一个要处理的节点后面循环就直接断链了。这个错误出现频率极高几乎每个新人都会踩一次。第四最后返回 head。left1 时head 已经不是新链表的头返回 dummy.next 才是安全的。这几种翻车基本都是“变量语义没定清楚”导致的不是逻辑多难。我自己的习惯是在代码注释里写明pre 是反转段前一个节点cur 是反转段第一个节点nxt 是当前要摘下的节点。写清楚之后错误率下降得非常明显。4. 递归解法从 reverseList 到 reverseN 再到区间反转4.1 递归反转整条链表是怎么“反直觉”地工作的递归反转整链表的经典代码如下ListNode* reverseList(ListNode* head) { if (!head || !head-next) return head; ListNode* newHead reverseList(head-next); head-next-next head; head-next nullptr; return newHead; }理解它的关键是递归函数 reverseList(head-next) 返回的是后面这一段反转后的新头。当递归一层层返回时head-next 已经是原链表的尾节点反转后它变成了后面这一段的新头。此时我们执行 head-next-next head让原来排在后面的节点反过来指向 head于是 head 接到了后面这一段的末尾。head-next 置空是因为 head 在反转后要成为整个链表的尾节点。这里有一个非常反直觉的点代码是先一路递归到最后一个节点然后在回溯过程中逐步调整每个节点的 next。它不需要知道链表长度因为递归栈已经把所有节点都压进去了。时间复杂度 O(n)但由于递归调用本身占用了系统栈空间复杂度是 O(n)。4.2 reverseN 为什么需要 successor如果只想反转前 N 个节点而不是整条链表上面的代码就不够用了。因为递归到底之后默认 head 是最后一个所以会把 head-next 置空。可如果只是反转前 N 个第 N 个节点后面还有一串节点需要保留这些节点不能丢。解决办法是额外记录一个 successor 指针ListNode* successor nullptr; ListNode* reverseN(ListNode* head, int n) { if (n 1) { successor head-next; return head; } ListNode* newHead reverseN(head-next, n - 1); head-next-next head; head-next successor; return newHead; }当 n 等于 1 时递归到达第 N 个节点。此时 head 就是这 N 个节点反转后的新头而 head-next 是原链表的第 N1 个节点。我们需要立刻把它保存到 successor 里否则回溯时第 N 个节点的 next 会被覆盖。每一层回溯时head-next 不再像整链反转那样置空而是统一指向 successor。这样第 1 到第 N 个节点反转完成后原来的第 1 个节点会接在 successor 上整个链表就是一个完整没有断裂的链表。这个 successor 变量是递归解法里最容易遗漏的点。很多人能写出 reverseList但写不出 reverseN就是因为忽略了“反转一小段和反转整条链表的区别在于后续还要接回去”。4.3 区间反转递归版的推导过程有了 reverseN区间反转就非常优雅了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; }这段代码需要顺着递归一层层看。假设链表是 1-2-3-4-5left2right4。第一层调用 reverseBetween(1, 2, 4)left 不等于 1于是执行 head-next reverseBetween(2, 1, 3)。也就是说“从节点 1 往后区间变成了 [1,3]”。第二层调用 reverseBetween(2, 1, 3)left 等于 1直接返回 reverseN(2, 3)。从节点 2 开始反转前 3 个节点结果是 4-3-2-5递归返回后这一整段被接到节点 1 的 next 上。最终链表变成 1-4-3-2-5。理解这段代码关键是要意识到递归的作用是“一层层跳过不需要反转的前段节点”。每次 left 和 right 同时减 1直到 left 变成 1问题就退化成了“从当前节点开始反转前 right 个节点”。而 reverseN 已经解决了这个子问题。Python 版本也不难class Solution: def reverseBetween(self, head: ListNode, left: int, right: int) - ListNode: self.successor None def reverseN(head: ListNode, n: int) - ListNode: if n 1: self.successor head.next return head new_head reverseN(head.next, n - 1) head.next.next head head.next self.successor return new_head if left 1: return reverseN(head, right) head.next self.reverseBetween(head.next, left - 1, right - 1) return head这里把 successor 作为实例属性来保存避免闭包变量作用域带来的麻烦。如果你用嵌套函数也可以在里面用 nonlocal 声明但实例属性在面试时更直观。4.4 递归的空间代价和面试取舍递归解法代码很短语义上也很漂亮适合向面试官解释“把大问题不断缩小为子问题”的思路。但代价是递归深度取决于 right而不是链表长度。如果区间很长比如 right 高达几十万递归栈可能直接溢出。实际工程或者性能敏感的代码几乎都会选迭代因为 O(1) 空间更稳。面试中比较好的策略是先用迭代写完并讲清楚然后主动提一句“如果用递归也能解核心是先实现 reverseN再在 left1 时调用它”展示自己对递归的理解。如果题目明确要求空间复杂度 O(1)那就必须收敛到迭代不要再讲递归了。5. 两种解法对比与边界用例复盘5.1 选迭代还是选递归我的实战建议笔试和竞赛我推荐迭代面试讲解我推荐把两个都掌握优先讲迭代。迭代的优点是空间复杂度 O(1)代码虽然长一点但每一步都好调试。递归的优点是代码短、语义清晰但需要额外维护 successor理解成本高一些。两种解法的时间复杂度都是 O(n)所以算法层面上没有高下之分区别在工程约束和表达成本。如果你准备面试建议练到这种程度给定 left 和 right能立刻在白板上写出迭代解法并且能画图解释为什么循环次数是 right-left。在此基础上再练递归解法重点把 reverseN 里的 successor 讲清楚。5.2 值得反复跑的六组用例刷题不能只跑一个示例就交差LeetCode 92 的坑几乎都在边界用例里。下面这组用例是我每次写完代码都会手动验证的用例期望结果考察点head[1,2,3,4,5], left2, right41-4-3-2-5常规中间区间head[1,2,3,4,5], left1, right44-3-2-1-5反转段包含头节点必须依赖 dummy 返回新头head[1,2,3], left1, right33-2-1反转整条链表与 206 呼应的特例head[1,2,3], left2, right21-2-3区间长度 1什么都不做head[1], left1, right11单节点链表head[]空链表空输入处理这六组跑完基本能暴露所有常见问题。尤其是 left1 和 rightlen 的组合最容易测出“返回了旧头节点”或“反转了多余节点”这两个 bug。5.3 从一次写挂的经历看指针调试有一回我在白板上手写迭代解法为了省事变量名用了 prev、start、end、tmp写到一半自己都分不清 prev 到底是“反转段前一个节点”还是“上一个节点”。结果代码里混用了排查了很久才发现问题根本不是逻辑想错了而是变量名模糊导致写出来和想的不一样。那次之后我定了一个规矩链表题代码里统一用 pre、cur、nxt 这三个名字。pre 表示反转段前驱cur 表示当前锚点nxt 表示下一秒要摘的节点。名字越贴近语义代码越不容易写错。这个小习惯在面试手写代码时特别重要。另一个坑是迭代解法里如果哪一步把 next 指针绕成了环程序会陷入死循环输出卡住。遇到这种情况不要慌着改逻辑先把 head 从头走一遍打印每个节点的值。如果发现某个节点的 next 指向了自己或者指回了前面的节点就说明问题出在“摘除和重挂”这一步。用例子手动模拟一遍通常不到十分钟就能定位。6. 从区间反转延伸出去变体题目与工程应用6.1 以 92 为原点的题目地图LeetCode 92 不是孤立的题它和一系列链表题构成了一条清晰的学习路线。LeetCode 206 反转链表整链反转是最基础的模板。LeetCode 92 反转链表 II区间反转就是 206 的限定版。LeetCode 24 两两交换链表中的节点相当于固定每两个节点为一组反转。LeetCode 25 K 个一组翻转链表每隔 K 个节点反转一段是 92 的加强版需要反复调用“区间反转”的逻辑同时维护好上一组的尾部和下一组的头部。如果 92 的迭代和递归都吃透再看 25 会轻松很多因为最后一题里每一轮操作都在复用 92 的流程定位 pre、记录下一组起点、反转当前段、拼接回去。差别只是需要用一个循环不断更新 left 和 right 的位置。6.2 链表反转在系统里的影子很多人觉得链表反转只是面试题实际工程用不上。其实不少系统里都藏着类似的“局部重组”逻辑。编辑器的 undo/redo 历史本质上是维护一条操作序列需要在某个位置撤销一段再插入新操作浏览器的前进后退历史也类似。再往底层看内存池的空闲块链表、哈希表拉链式结构、操作系统里进程控制块的双向链表维护都离不开“定位节点、摘除节点、重新挂接”这一套基本功。区别在于工程代码里你不会直接写一个 reverseBetween但你会经常处理“在指定位置插入节点”和“删除一段节点”这种操作。LeetCode 92 训练的就是你在这些操作中保持指针关系清晰的能力。画图、命名、测试边界这套习惯会直接迁移到真实代码里。6.3 三轮练习法把这道题吃成肌肉记忆最后给一个实操性很强的练习建议。第一遍只练迭代解法画图走完上面说的六组用例直到能不看题解写出来。第二遍练递归解法重点复述 reverseN 里 successor 的作用以及 reverseBetween 为什么在 left1 时直接调 reverseN。第三遍合上所有代码用空白编辑器从零开始写两道题LeetCode 92 和 LeetCode 25。如果能顺利写完链表反转这一系的基本功就算过关了。我在实际准备面试时LeetCode 92 的迭代和递归各写了不下五遍。到了后来几乎可以闭眼默写不是因为记性好而是每一步指针变化的画面已经刻在脑子里了。希望这篇拆解也能帮你找到那种“看见链表结构”的感觉。