LeetCode 206 反转链表是所有链表类题目里出场率最高的一道没有之一。用 JavaScript 刷这道题的人特别多但真正能把它讲清楚的人很少。我见过太多人看题解时秒懂合上代码自己写却连指针指哪都搞不清楚也见过候选人能默写出代码却解释不了为什么返回的是 prev。这篇文章不仅给你三种写法还会把每一步指针变化的来龙去脉讲明白适合刚接触链表的初学者也适合准备面试想把这题形成肌肉记忆的同学。这题本身不复杂复杂的是人的直觉。我们从小到大接触的数据结构大多是数组数组的反转就是 index 头尾互换可链表没有 index你只能通过 next 一个节点一个节点地爬。反转链表要做的不是把数据搬来搬去而是把所有 next 指向调个头。这个调头的动作听起来简单实际动手时牵扯到引用、临时变量、边界条件任何一个环节没想清楚代码就会在某个隐蔽的用例上报错。所以我不建议直接背代码而是先把链表的存储方式在脑子里建模再去看任何解法都会豁然开朗。1. 题干拆解反转链表到底在考什么基本功1.1 题目要求与 ListNode 的定义LeetCode 206 的原始描述很简练给你单链表的头节点 head 请你反转链表并返回反转后的链表。输入是一个串好的链表输出是反转后的链表头节点。比如 1 - 2 - 3 - 4 - 5 - null反转后要变成 5 - 4 - 3 - 2 - 1 - null。看起来只是把箭头方向倒过来一遍但真要动手写第一步就得先弄清楚链表节点在 JavaScript 里长什么样。在 JavaScript 的 LeetCode 环境里链表节点已经定义好了你在编辑器里看不到这段代码但它是真实存在的function ListNode(val, next) { this.val (val undefined ? 0 : val); this.next (next undefined ? null : next); }这里的 val 是节点存的值next 是指向下一个节点的引用。看到 next 就记住一件事它不是下一个节点的值而是下一个节点对象本身。所有链表的操作本质上都是读写这个 next 引用以及决定当前变量指向哪个节点。这个认知特别重要后面很多坑都出在把节点和节点的值混为一谈。因为输入参数本身就是 null 或一个节点对象所以第一件要处理的事情就是空链表和单节点链表。反转一个空链表结果还是空链表反转一个只有头节点的链表返回的还是它自己。这两种情况是所有解法共同的 base case后面的递归版代码里你会反复看到head null || head.next null这个判断。1.2 边界条件是这题的隐藏考点很多人在 while 循环里写着写着就容易越界原因就是没有把边界条件想清楚。反转链表有一个特别容易犯的错误循环结束后不知道该返回谁。这里直接给出结论后面会解释为什么——迭代法返回的是 prev不是 head。因为当 current 跑到 null 时prev 恰好停在原链表的尾节点也就是反转后的新头节点。另一个隐藏考点是原链表的头节点在反转后会变成尾节点它的 next 必须指向 null。如果你把指针改来改去最后忘了把 head.next 置空链表就会形成环LeetCode 会报 runtime error 或者直接超时。初学者最容易漏的就是这一步因为在草稿纸上画图时注意力全放在中间节点的指针翻转上头尾两个特殊节点反而被忽略。边界条件的价值不在于代码多难写而在于你想不想得到。很多题目核心逻辑写对了边界一错就是大规模扣分。反转链表这题的边界值其实只有两个链表为空、链表只有一个节点。只要你的解法能正确处理这两种情况就说明你对循环退出条件是有把握的而不是碰巧跑通了一个常规用例。1.3 为什么它不是一道会背代码就行的题这道题之所以被各大公司反复拿来考是因为它用最少的代码量考察了链表最核心的三个基本功遍历链表、修改指针、处理边界。任何一项不扎实写出来的代码都会在测试用例上露出破绽。另外这题有迭代、递归、尾递归等多种解法面试官可以顺着你写的解法继续追问考察你对时间复杂度和空间复杂度的理解。所以它常常不是一道独立的题而是后面更难题目的敲门砖。比如反转链表的前 N 个节点反转链表的一部分K 个一组翻转链表都建立在今天这个基础操作之上。把这题吃透等于把链表操作的地基打了一半。2. 迭代解法三个指针像流水线一样逐个翻转2.1 为什么必须准备三个指针迭代法的核心问题是遍历一个链表只需要一个指针 head 或 current 就够了但反转链表时你要做的操作是current.next prev也就是把当前节点的下一个节点改成前面的节点。问题来了一旦 current.next 被改掉原来 current 后面的那个节点就再也找不到了。所以在改指针之前必须先用另一个变量把后面的节点存下来。这就是三个指针的来源prev已经反转好的部分的头节点初始为 nullcurrent当前要处理反转的节点初始为 headnextTempcurrent 原本的下一个节点用于保存现场我常用一个生活比喻你在搬家要把一排书从旧架子上按相反的顺序搬到另一个架子上。每次你只能从旧架子上取一本书在把它放到新架子之前必须先把旧架子上下一本书的位置记住否则一转身就不知道下一本在哪了。这里的记住下一本书的位置就是 nextTemp 干的事。用生活的比喻会让面试时讲代码顺畅很多我建议你自己也找一个能说得顺口的类比面试时边说边画比闷头写代码要加分得多。2.2 完整代码与逐轮指针变化跟踪迭代版本的代码非常短核心循环只有四行var reverseList function(head) { let prev null; let current head; while (current ! null) { const nextTemp current.next; // 1. 先保存下一个节点 current.next prev; // 2. 反转指针 prev current; // 3. prev 前进 current nextTemp; // 4. current 前进 } return prev; };我用一个长度为 3 的链表 1 - 2 - 3 - null 来走一遍每一步都盯住三个变量的指向轮次进入循环时操作后 prev操作后 current操作后链表状态0prev null, current 1--1 - 2 - 3 - null1nextTemp 2; 1.next null12null - 1 ; 2 - 3 - null2nextTemp 3; 2.next 123null - 1 - 2 ; 3 - null3nextTemp null; 3.next 23nullnull - 1 - 2 - 3循环结束后 current 为 nullprev 指向节点 3也就是反转后的新头节点所以返回 prev。这张表建议你自己也在纸上画一遍很多人肉眼看代码觉得懂了真正手动跟踪一轮才会发现自己对第 2 步和第 3 步的顺序是模糊的。记住一个原则先保存后修改不然会丢节点。2.3 复杂度分析与面试讲法时间复杂度 O(n)因为每个节点恰好被访问一次n 是链表长度。空间复杂度 O(1)因为只用了固定数量的额外变量没有根据输入规模增长的存储。在面试里把这题讲好我通常会按这个顺序来先说是用迭代法声明用三个指针思路是逐个反转每个节点的 next 方向画一个 1 - 2 - 3 的例子重点演示第一轮循环中先存 nextTemp再改 current.next这一下强调边界情况空链表和单节点链表会直接跳过循环返回 prev 依然正确最后提一句空间复杂度是 O(1)因为面试官通常就会接着问这个。用不用while (current)代替while (current ! null)都行JavaScript 里对象是 truthynull 是 falsy所以while (current)也能跑。但我推荐写完整判断一来语义清楚二来面试时不会因为省略写法给人留下图省事的印象。3. 递归解法让子问题自己搞定后面一段3.1 递归公式是怎么想出来的迭代法是从前往后依次处理递归法正好相反它先把后面的所有节点看成一个整体子问题假设子问题已经反转好了再处理当前节点和子问题之间的连接。这是很多初学者觉得递归难的根本原因你习惯用循环模拟过程但递归要求你先相信函数能自己解决问题然后只关心当前这一层和子问题结果之间的关系。递归公式可以写成这样reverseList(head)的结果如果 head 是 null 或 head.next 是 null直接返回 head否则先得到newHead reverseList(head.next)这表示把 head 后面那一整段都反转好并返回新的头节点然后把head.next.next指向 head也就是让原本的下一个节点反过来指向 head再让 head.next 指向 null把原头节点变成新的尾节点。对应代码var reverseList function(head) { if (head null || head.next null) { return head; } const newHead reverseList(head.next); head.next.next head; head.next null; return newHead; };递归和迭代在思路上最大的不同是迭代版在处理节点递归版在信任子问题。你不用手动维护 prev 和 current子问题返回后你只需要处理当前 head 和它下一个节点之间的连接关系。3.2 最难理解的一行head.next.next head第一次看到head.next.next head的人几乎都会懵这行到底在做什么我建议你把它拆开读head.next 是原来的下一个节点head.next.next 是原来的下一个节点的 next 指向。这行代码的意思是让原来的下一个节点把它的 next 指向当前 head也就是完成一次反转。举个例子链表 1 - 2 - 3。在reverseList(1)这一层里head 是节点 1head.next 是节点 2。执行head.next.next head就是把 2.next 从原来的 3 改成 1。这时候链表确实有点混乱1.next 还是 22.next 变成 13 原封不动。紧接着head.next null会把 1.next 断开链表就变成 null - 1 - 2 - 3。节点 1 和节点 2 之间的箭头已经反过来了剩下的节点 3 会在更深层的递归里处理。为什么必须置head.next null因为递归结束后 head 会变成整条链表的尾节点尾节点的 next 必须是 null。如果你不置空轻则链表形成环重则 LeetCode 直接超时。这个细节和迭代法里原头节点要指向 null是同一个道理只是递归里它藏在回溯的最后。凡是递归解法把这里漏掉的人至少占一半。3.3 递归调用栈回溯的完整过程我再用 1 - 2 - 3 - null 走一遍完整过程这次从调用栈的角度看reverseList(1)不满足 base case调用reverseList(2)reverseList(2)不满足 base case调用reverseList(3)reverseList(3)满足 base case3.next null直接返回节点 3不用做任何翻转回到reverseList(2)这一层newHead 3执行 2.next.next 2即 3.next 2再执行 2.next null此时链表变成 3 - 2返回 newHead 3回到reverseList(1)这一层newHead 仍然是 31.next 还是 2。执行 1.next.next 1其中 1.next.next 就是 2.next目前 2.next 是 null所以这句等价于 2.next 1再执行 1.next null断开原来的正向连接最终链表变成 3 - 2 - 1 - null返回 newHead 3。整个过程中最反直觉的地方在于你以为递归是在往深处走的时候完成反转实际上真正的反转发生在回溯阶段。每一层递归返回时当前节点才跟它的下一个节点完成一次指针交换。所以递归版的时间复杂度也是 O(n)每个节点被访问一次空间复杂度是 O(n)因为递归的每一层都占用调用栈空间链表多长调用栈就有多深。JavaScript 引擎对递归深度有限制理论上当链表特别长的时候递归可能不如迭代稳。LeetCode 的测试集一般不会到爆栈的程度但如果你在面试中写了递归版主动提一句空间复杂度是 O(n)因为调用栈会显得考虑周全。4. 迭代、递归和函数式写法怎么选4.1 三种写法的代码对比把三种写法放在一起看特征很鲜明。迭代版var reverseList function(head) { let prev null; let current head; while (current ! null) { const nextTemp current.next; current.next prev; prev current; current nextTemp; } return prev; };递归版var reverseList function(head) { if (head null || head.next null) return head; const newHead reverseList(head.next); head.next.next head; head.next null; return newHead; };还有一种网上常看到的一行流用 ES6 的解构赋值var reverseList function(head) { let [prev, current] [null, head]; while (current) { [current.next, prev, current] [prev, current, current.next]; } return prev; };这个写法能跑而且利用了 JS 解构赋值右侧表达式先求值、再批量赋值的特性右侧的 current.next 是修改前的旧值所以赋值时不会把指针改乱。但可读性比较差我一般不推荐在面试中用除非面试官是 JS 重度用户并明确表示想看你秀花活。4.2 复杂度与可读性的综合对比我用一张表总结维度迭代法递归法一行流时间复杂度O(n)O(n)O(n)空间复杂度O(1)O(n)O(1)代码量短更短最短可读性高适合第一遍学中需要理解递归低必须懂解构求值顺序调试难度低循环过程直观高依赖回溯中单行不好打断点面试推荐度五星四星一星到两星个人经验是优先掌握迭代它是所有解法的基础而且 O(1) 空间没有副作用。递归也要会写很多面试官会问能不能换个思路或者如果链表特别长递归有什么问题这时候递归就是最好的备选而且它体现你对问题分解的理解。一行流私底下玩可以面试里除非你们已经聊到 JavaScript 语言特性否则它带来的风险大于收益。一个候选人如果在白板上写出解构一行流还得跟面试官解释半天语法反而把实现思路掩盖掉了。4.3 关于一行代码写法的评价我必须承认用解构赋值写反转链表确实很JavaScript因为其他语言没法这么简洁。但简洁不等于适合面试更不等于适合教学。我在看别人代码时发现一个规律一行流版本最容易在多人协作的项目里引发歧义reviewer 要花不少时间确认赋值顺序没坑。算法题也一样清晰比炫技重要。如果你真的想扩展点新东西可以思考一下尾递归写法var reverseList function(head, prev null) { if (head null) return prev; const nextTemp head.next; head.next prev; return reverseList(nextTemp, head); };这个版本把 prev 作为参数传递本质上是迭代的递归翻版。在支持尾调用优化的环境里它的空间复杂度可以是 O(1)但 JavaScript 的尾调用优化只在严格模式下部分引擎支持一般来说默认环境不保证所以不要把尾递归一定不爆栈当成结论。理解它把状态放在参数里的思路倒是有助于加深对递归的认识。5. JavaScript 环境里容易踩的坑和调试方法5.1 引用类型与指针修改的底层直觉JavaScript 里对象是引用类型链表节点用对象实现所以指针其实是对象引用。很多人写反转链表时报错或者死循环是因为心里没有把变量和对象分开。current.next prev改的不是变量 current而是 current 指向的那个对象的 next 属性。理解这一点非常关键你在循环里移动的是哪个对象是当前处理对象而不是把对象本身变来变去。我用一句简单的话总结链表节点是盒子变量是手电筒。current 这个手电筒照在哪个盒子上你改的就是那个盒子的标签而不是手电筒本身。每一轮循环你把 current 的 next 标签换成 prev 指向的盒子然后把手电筒往前移到 nextTemp 指向的盒子。脑子里有了这个画面写代码时就不容易把自己绕晕。5.2 用 const / let 的细节还有一个容易被忽略的 JS 细节循环体里的 nextTemp 用 const 还是 let这题里 nextTemp 在循环体内声明每轮循环都创建新的常量绑定所以用 const 没问题但如果你把 nextTemp 声明在循环外面就得用 let因为每轮都要重新赋值。我习惯把 nextTemp 写在循环体内并用 const一方面作用域更干净另一方面向读代码的人传达这个变量这轮循环内不会变的意图。prev 和 current 必须用 let因为它们的指向会变。如果你写了const prev null后面prev current直接抛 TypeError。这些细节在 JavaScript 里属于静态检查就能发现的错误但面试手写代码没有编译器提示平时养成好习惯就很重要。关于while (current ! null)还是while (current)前面提过两种都能跑。从严谨角度我推荐前者因为它明确表达了边界判断是判断是否为 null而不是依赖真值转换。链表的结束标志是 null不是 undefined也不是 0。LeetCode 的 ListNode 默认把 next 设为 null你从输入里拿到的链表不会出现 next 为 undefined 的情况但如果自己构造测试数据要确保用 null 表示空节点。5.3 自测辅助函数与本地调试LeetCode 的输入输出是标准化的本地想快速验证代码可以自己写两个小工具函数把数组转成链表、把链表转回数组function arrayToList(arr) { const dummy new ListNode(0); let p dummy; for (const val of arr) { p.next new ListNode(val); p p.next; } return dummy.next; } function listToArray(head) { const result []; while (head ! null) { result.push(head.val); head head.next; } return result; }有了这两个函数测试就非常直观console.log(listToArray(reverseList(arrayToList([1, 2, 3, 4, 5])))); // 期望输出 [5, 4, 3, 2, 1]如果结果不对我建议先在代码里加 console.log 打印 prev、current、nextTemp 每一轮的值对照自己画的过程图找偏差。实际经验是80% 的错误都集中在头节点的 next 没有置空或者 while 循环结束后返回了 current 而不是 prev。这两种错一旦你知道检查方向几秒钟就能定位。5.4 LeetCode 提交时的实际表现与心态题目本身的输入规模不大迭代法和递归法在 LeetCode 上跑起来耗时都很短。你可能会看到运行时间打败 80% 之类的数据但在这种简单题上运行时间的差异更多是服务器波动和测试集长度决定的不必追求打败 100%。真正该关注的是代码是否正确、边界是否处理完整、空间复杂度有没有多余开销。我遇到过的真实场景是候选人写出了正确代码但当面试官问每一步指针为什么要这样移动时候选人只能说我是背的这个模板很经典。这种回答比写错代码更让人惋惜。所以我的建议是刷完这道题后至少做到能不看代码用笔在纸上把 1 - 2 - 3 - 4 的迭代过程完整画出来。能做到这一步这道题对你来说才算真正结束。
LeetCode 206反转链表：JavaScript三种解法与指针详解
LeetCode 206 反转链表是所有链表类题目里出场率最高的一道没有之一。用 JavaScript 刷这道题的人特别多但真正能把它讲清楚的人很少。我见过太多人看题解时秒懂合上代码自己写却连指针指哪都搞不清楚也见过候选人能默写出代码却解释不了为什么返回的是 prev。这篇文章不仅给你三种写法还会把每一步指针变化的来龙去脉讲明白适合刚接触链表的初学者也适合准备面试想把这题形成肌肉记忆的同学。这题本身不复杂复杂的是人的直觉。我们从小到大接触的数据结构大多是数组数组的反转就是 index 头尾互换可链表没有 index你只能通过 next 一个节点一个节点地爬。反转链表要做的不是把数据搬来搬去而是把所有 next 指向调个头。这个调头的动作听起来简单实际动手时牵扯到引用、临时变量、边界条件任何一个环节没想清楚代码就会在某个隐蔽的用例上报错。所以我不建议直接背代码而是先把链表的存储方式在脑子里建模再去看任何解法都会豁然开朗。1. 题干拆解反转链表到底在考什么基本功1.1 题目要求与 ListNode 的定义LeetCode 206 的原始描述很简练给你单链表的头节点 head 请你反转链表并返回反转后的链表。输入是一个串好的链表输出是反转后的链表头节点。比如 1 - 2 - 3 - 4 - 5 - null反转后要变成 5 - 4 - 3 - 2 - 1 - null。看起来只是把箭头方向倒过来一遍但真要动手写第一步就得先弄清楚链表节点在 JavaScript 里长什么样。在 JavaScript 的 LeetCode 环境里链表节点已经定义好了你在编辑器里看不到这段代码但它是真实存在的function ListNode(val, next) { this.val (val undefined ? 0 : val); this.next (next undefined ? null : next); }这里的 val 是节点存的值next 是指向下一个节点的引用。看到 next 就记住一件事它不是下一个节点的值而是下一个节点对象本身。所有链表的操作本质上都是读写这个 next 引用以及决定当前变量指向哪个节点。这个认知特别重要后面很多坑都出在把节点和节点的值混为一谈。因为输入参数本身就是 null 或一个节点对象所以第一件要处理的事情就是空链表和单节点链表。反转一个空链表结果还是空链表反转一个只有头节点的链表返回的还是它自己。这两种情况是所有解法共同的 base case后面的递归版代码里你会反复看到head null || head.next null这个判断。1.2 边界条件是这题的隐藏考点很多人在 while 循环里写着写着就容易越界原因就是没有把边界条件想清楚。反转链表有一个特别容易犯的错误循环结束后不知道该返回谁。这里直接给出结论后面会解释为什么——迭代法返回的是 prev不是 head。因为当 current 跑到 null 时prev 恰好停在原链表的尾节点也就是反转后的新头节点。另一个隐藏考点是原链表的头节点在反转后会变成尾节点它的 next 必须指向 null。如果你把指针改来改去最后忘了把 head.next 置空链表就会形成环LeetCode 会报 runtime error 或者直接超时。初学者最容易漏的就是这一步因为在草稿纸上画图时注意力全放在中间节点的指针翻转上头尾两个特殊节点反而被忽略。边界条件的价值不在于代码多难写而在于你想不想得到。很多题目核心逻辑写对了边界一错就是大规模扣分。反转链表这题的边界值其实只有两个链表为空、链表只有一个节点。只要你的解法能正确处理这两种情况就说明你对循环退出条件是有把握的而不是碰巧跑通了一个常规用例。1.3 为什么它不是一道会背代码就行的题这道题之所以被各大公司反复拿来考是因为它用最少的代码量考察了链表最核心的三个基本功遍历链表、修改指针、处理边界。任何一项不扎实写出来的代码都会在测试用例上露出破绽。另外这题有迭代、递归、尾递归等多种解法面试官可以顺着你写的解法继续追问考察你对时间复杂度和空间复杂度的理解。所以它常常不是一道独立的题而是后面更难题目的敲门砖。比如反转链表的前 N 个节点反转链表的一部分K 个一组翻转链表都建立在今天这个基础操作之上。把这题吃透等于把链表操作的地基打了一半。2. 迭代解法三个指针像流水线一样逐个翻转2.1 为什么必须准备三个指针迭代法的核心问题是遍历一个链表只需要一个指针 head 或 current 就够了但反转链表时你要做的操作是current.next prev也就是把当前节点的下一个节点改成前面的节点。问题来了一旦 current.next 被改掉原来 current 后面的那个节点就再也找不到了。所以在改指针之前必须先用另一个变量把后面的节点存下来。这就是三个指针的来源prev已经反转好的部分的头节点初始为 nullcurrent当前要处理反转的节点初始为 headnextTempcurrent 原本的下一个节点用于保存现场我常用一个生活比喻你在搬家要把一排书从旧架子上按相反的顺序搬到另一个架子上。每次你只能从旧架子上取一本书在把它放到新架子之前必须先把旧架子上下一本书的位置记住否则一转身就不知道下一本在哪了。这里的记住下一本书的位置就是 nextTemp 干的事。用生活的比喻会让面试时讲代码顺畅很多我建议你自己也找一个能说得顺口的类比面试时边说边画比闷头写代码要加分得多。2.2 完整代码与逐轮指针变化跟踪迭代版本的代码非常短核心循环只有四行var reverseList function(head) { let prev null; let current head; while (current ! null) { const nextTemp current.next; // 1. 先保存下一个节点 current.next prev; // 2. 反转指针 prev current; // 3. prev 前进 current nextTemp; // 4. current 前进 } return prev; };我用一个长度为 3 的链表 1 - 2 - 3 - null 来走一遍每一步都盯住三个变量的指向轮次进入循环时操作后 prev操作后 current操作后链表状态0prev null, current 1--1 - 2 - 3 - null1nextTemp 2; 1.next null12null - 1 ; 2 - 3 - null2nextTemp 3; 2.next 123null - 1 - 2 ; 3 - null3nextTemp null; 3.next 23nullnull - 1 - 2 - 3循环结束后 current 为 nullprev 指向节点 3也就是反转后的新头节点所以返回 prev。这张表建议你自己也在纸上画一遍很多人肉眼看代码觉得懂了真正手动跟踪一轮才会发现自己对第 2 步和第 3 步的顺序是模糊的。记住一个原则先保存后修改不然会丢节点。2.3 复杂度分析与面试讲法时间复杂度 O(n)因为每个节点恰好被访问一次n 是链表长度。空间复杂度 O(1)因为只用了固定数量的额外变量没有根据输入规模增长的存储。在面试里把这题讲好我通常会按这个顺序来先说是用迭代法声明用三个指针思路是逐个反转每个节点的 next 方向画一个 1 - 2 - 3 的例子重点演示第一轮循环中先存 nextTemp再改 current.next这一下强调边界情况空链表和单节点链表会直接跳过循环返回 prev 依然正确最后提一句空间复杂度是 O(1)因为面试官通常就会接着问这个。用不用while (current)代替while (current ! null)都行JavaScript 里对象是 truthynull 是 falsy所以while (current)也能跑。但我推荐写完整判断一来语义清楚二来面试时不会因为省略写法给人留下图省事的印象。3. 递归解法让子问题自己搞定后面一段3.1 递归公式是怎么想出来的迭代法是从前往后依次处理递归法正好相反它先把后面的所有节点看成一个整体子问题假设子问题已经反转好了再处理当前节点和子问题之间的连接。这是很多初学者觉得递归难的根本原因你习惯用循环模拟过程但递归要求你先相信函数能自己解决问题然后只关心当前这一层和子问题结果之间的关系。递归公式可以写成这样reverseList(head)的结果如果 head 是 null 或 head.next 是 null直接返回 head否则先得到newHead reverseList(head.next)这表示把 head 后面那一整段都反转好并返回新的头节点然后把head.next.next指向 head也就是让原本的下一个节点反过来指向 head再让 head.next 指向 null把原头节点变成新的尾节点。对应代码var reverseList function(head) { if (head null || head.next null) { return head; } const newHead reverseList(head.next); head.next.next head; head.next null; return newHead; };递归和迭代在思路上最大的不同是迭代版在处理节点递归版在信任子问题。你不用手动维护 prev 和 current子问题返回后你只需要处理当前 head 和它下一个节点之间的连接关系。3.2 最难理解的一行head.next.next head第一次看到head.next.next head的人几乎都会懵这行到底在做什么我建议你把它拆开读head.next 是原来的下一个节点head.next.next 是原来的下一个节点的 next 指向。这行代码的意思是让原来的下一个节点把它的 next 指向当前 head也就是完成一次反转。举个例子链表 1 - 2 - 3。在reverseList(1)这一层里head 是节点 1head.next 是节点 2。执行head.next.next head就是把 2.next 从原来的 3 改成 1。这时候链表确实有点混乱1.next 还是 22.next 变成 13 原封不动。紧接着head.next null会把 1.next 断开链表就变成 null - 1 - 2 - 3。节点 1 和节点 2 之间的箭头已经反过来了剩下的节点 3 会在更深层的递归里处理。为什么必须置head.next null因为递归结束后 head 会变成整条链表的尾节点尾节点的 next 必须是 null。如果你不置空轻则链表形成环重则 LeetCode 直接超时。这个细节和迭代法里原头节点要指向 null是同一个道理只是递归里它藏在回溯的最后。凡是递归解法把这里漏掉的人至少占一半。3.3 递归调用栈回溯的完整过程我再用 1 - 2 - 3 - null 走一遍完整过程这次从调用栈的角度看reverseList(1)不满足 base case调用reverseList(2)reverseList(2)不满足 base case调用reverseList(3)reverseList(3)满足 base case3.next null直接返回节点 3不用做任何翻转回到reverseList(2)这一层newHead 3执行 2.next.next 2即 3.next 2再执行 2.next null此时链表变成 3 - 2返回 newHead 3回到reverseList(1)这一层newHead 仍然是 31.next 还是 2。执行 1.next.next 1其中 1.next.next 就是 2.next目前 2.next 是 null所以这句等价于 2.next 1再执行 1.next null断开原来的正向连接最终链表变成 3 - 2 - 1 - null返回 newHead 3。整个过程中最反直觉的地方在于你以为递归是在往深处走的时候完成反转实际上真正的反转发生在回溯阶段。每一层递归返回时当前节点才跟它的下一个节点完成一次指针交换。所以递归版的时间复杂度也是 O(n)每个节点被访问一次空间复杂度是 O(n)因为递归的每一层都占用调用栈空间链表多长调用栈就有多深。JavaScript 引擎对递归深度有限制理论上当链表特别长的时候递归可能不如迭代稳。LeetCode 的测试集一般不会到爆栈的程度但如果你在面试中写了递归版主动提一句空间复杂度是 O(n)因为调用栈会显得考虑周全。4. 迭代、递归和函数式写法怎么选4.1 三种写法的代码对比把三种写法放在一起看特征很鲜明。迭代版var reverseList function(head) { let prev null; let current head; while (current ! null) { const nextTemp current.next; current.next prev; prev current; current nextTemp; } return prev; };递归版var reverseList function(head) { if (head null || head.next null) return head; const newHead reverseList(head.next); head.next.next head; head.next null; return newHead; };还有一种网上常看到的一行流用 ES6 的解构赋值var reverseList function(head) { let [prev, current] [null, head]; while (current) { [current.next, prev, current] [prev, current, current.next]; } return prev; };这个写法能跑而且利用了 JS 解构赋值右侧表达式先求值、再批量赋值的特性右侧的 current.next 是修改前的旧值所以赋值时不会把指针改乱。但可读性比较差我一般不推荐在面试中用除非面试官是 JS 重度用户并明确表示想看你秀花活。4.2 复杂度与可读性的综合对比我用一张表总结维度迭代法递归法一行流时间复杂度O(n)O(n)O(n)空间复杂度O(1)O(n)O(1)代码量短更短最短可读性高适合第一遍学中需要理解递归低必须懂解构求值顺序调试难度低循环过程直观高依赖回溯中单行不好打断点面试推荐度五星四星一星到两星个人经验是优先掌握迭代它是所有解法的基础而且 O(1) 空间没有副作用。递归也要会写很多面试官会问能不能换个思路或者如果链表特别长递归有什么问题这时候递归就是最好的备选而且它体现你对问题分解的理解。一行流私底下玩可以面试里除非你们已经聊到 JavaScript 语言特性否则它带来的风险大于收益。一个候选人如果在白板上写出解构一行流还得跟面试官解释半天语法反而把实现思路掩盖掉了。4.3 关于一行代码写法的评价我必须承认用解构赋值写反转链表确实很JavaScript因为其他语言没法这么简洁。但简洁不等于适合面试更不等于适合教学。我在看别人代码时发现一个规律一行流版本最容易在多人协作的项目里引发歧义reviewer 要花不少时间确认赋值顺序没坑。算法题也一样清晰比炫技重要。如果你真的想扩展点新东西可以思考一下尾递归写法var reverseList function(head, prev null) { if (head null) return prev; const nextTemp head.next; head.next prev; return reverseList(nextTemp, head); };这个版本把 prev 作为参数传递本质上是迭代的递归翻版。在支持尾调用优化的环境里它的空间复杂度可以是 O(1)但 JavaScript 的尾调用优化只在严格模式下部分引擎支持一般来说默认环境不保证所以不要把尾递归一定不爆栈当成结论。理解它把状态放在参数里的思路倒是有助于加深对递归的认识。5. JavaScript 环境里容易踩的坑和调试方法5.1 引用类型与指针修改的底层直觉JavaScript 里对象是引用类型链表节点用对象实现所以指针其实是对象引用。很多人写反转链表时报错或者死循环是因为心里没有把变量和对象分开。current.next prev改的不是变量 current而是 current 指向的那个对象的 next 属性。理解这一点非常关键你在循环里移动的是哪个对象是当前处理对象而不是把对象本身变来变去。我用一句简单的话总结链表节点是盒子变量是手电筒。current 这个手电筒照在哪个盒子上你改的就是那个盒子的标签而不是手电筒本身。每一轮循环你把 current 的 next 标签换成 prev 指向的盒子然后把手电筒往前移到 nextTemp 指向的盒子。脑子里有了这个画面写代码时就不容易把自己绕晕。5.2 用 const / let 的细节还有一个容易被忽略的 JS 细节循环体里的 nextTemp 用 const 还是 let这题里 nextTemp 在循环体内声明每轮循环都创建新的常量绑定所以用 const 没问题但如果你把 nextTemp 声明在循环外面就得用 let因为每轮都要重新赋值。我习惯把 nextTemp 写在循环体内并用 const一方面作用域更干净另一方面向读代码的人传达这个变量这轮循环内不会变的意图。prev 和 current 必须用 let因为它们的指向会变。如果你写了const prev null后面prev current直接抛 TypeError。这些细节在 JavaScript 里属于静态检查就能发现的错误但面试手写代码没有编译器提示平时养成好习惯就很重要。关于while (current ! null)还是while (current)前面提过两种都能跑。从严谨角度我推荐前者因为它明确表达了边界判断是判断是否为 null而不是依赖真值转换。链表的结束标志是 null不是 undefined也不是 0。LeetCode 的 ListNode 默认把 next 设为 null你从输入里拿到的链表不会出现 next 为 undefined 的情况但如果自己构造测试数据要确保用 null 表示空节点。5.3 自测辅助函数与本地调试LeetCode 的输入输出是标准化的本地想快速验证代码可以自己写两个小工具函数把数组转成链表、把链表转回数组function arrayToList(arr) { const dummy new ListNode(0); let p dummy; for (const val of arr) { p.next new ListNode(val); p p.next; } return dummy.next; } function listToArray(head) { const result []; while (head ! null) { result.push(head.val); head head.next; } return result; }有了这两个函数测试就非常直观console.log(listToArray(reverseList(arrayToList([1, 2, 3, 4, 5])))); // 期望输出 [5, 4, 3, 2, 1]如果结果不对我建议先在代码里加 console.log 打印 prev、current、nextTemp 每一轮的值对照自己画的过程图找偏差。实际经验是80% 的错误都集中在头节点的 next 没有置空或者 while 循环结束后返回了 current 而不是 prev。这两种错一旦你知道检查方向几秒钟就能定位。5.4 LeetCode 提交时的实际表现与心态题目本身的输入规模不大迭代法和递归法在 LeetCode 上跑起来耗时都很短。你可能会看到运行时间打败 80% 之类的数据但在这种简单题上运行时间的差异更多是服务器波动和测试集长度决定的不必追求打败 100%。真正该关注的是代码是否正确、边界是否处理完整、空间复杂度有没有多余开销。我遇到过的真实场景是候选人写出了正确代码但当面试官问每一步指针为什么要这样移动时候选人只能说我是背的这个模板很经典。这种回答比写错代码更让人惋惜。所以我的建议是刷完这道题后至少做到能不看代码用笔在纸上把 1 - 2 - 3 - 4 的迭代过程完整画出来。能做到这一步这道题对你来说才算真正结束。