★ FEATURED ARTICLE 1. 章节定位3.1背后到底考什么1.1 为什么链表是面试算法的高频区链表这类题在面试里出现频率极高不是因为它难而是因为它特别适合考察一个程序员的基本功。你写删除节点、反转链表、找中间节点的时候暴露的是三件事对引用和内存关系的理解、对边界条件的敏感度、以及用代码把思路翻译出来的能力。这三样东西几乎没法靠背模板糊弄过去。拿Kotlin来说面试官看你的链表代码不只是看对不对还会暗暗观察你是不是真的搞懂了JVM层面的对象引用。Kotlin没有C/C那种指针语法但next这个字段本质就是一个引用。你写curr.next prev的时候到底改的是哪个对象的字段两个变量同时指向同一个节点时改一个会不会影响另一个这些问题想不清楚代码就容易写得磕磕绊绊。3.1作为链表专题的第一小节定位就是帮你把这些基本功夯实。很多候选人一上来就刷困难题结果链表的基本操作都写不利索面试时被一个反转链表问住心态直接崩了。如果你也在准备Kotlin方向的岗位面试或者想系统梳理链表的解题套路这个章节值得认真过一遍。1.2 3.1章节的内容安排这一节的核心内容可以概括成一句话链表题的起点是反转反转的周边是一整个家族。先从最基本的单链表反转开始把迭代和递归两种写法吃透然后延展到区间反转、K个一组反转、回文链表判定这些经典变体。为什么从反转开始因为反转题覆盖了链表操作中最关键的两个动作改引用方向、保存被覆盖的引用。这两个动作是所有链表题的地基。你后面做删除倒数第N个节点、合并有序链表、判断环形链表本质上都在反复做这两件事。另外提一句这一节里的代码我都用Kotlin写。Kotlin写链表题和Java有区别但核心思路是一样的。如果你平时用的是Java把语法上的差异抹掉之后整个解题框架完全可以平移过去。2. Kotlin写链表题和Java的关键差别2.1 节点类定义与可变性Java里定义链表节点最常见的是这样class ListNode { int val; ListNode next; ListNode(int val) { this.val val; } }Kotlin里我一般这样写class ListNode(var value: Int) { var next: ListNode? null }看起来只是语法差异但有两点值得注意。第一Kotlin的var next默认是public的可以直接访问不需要写getter/setter。第二next的类型是ListNode?带上了可空标记。这在写算法题时是一种优势编译器会强制你处理空值分支很多因为忘记判空而导致的NullPointerException在编译期就被拦下来了。有同学问过我要不要用data class定义节点。我的建议是不要。data class会生成equals、hashCode、toString等方法写业务代码很爽但在算法题里这些额外生成的方法反而可能干扰你对引用相等和值相等的判断。链表题里判断两个节点是否相同用的是引用相等而data class重写的equals比的是值。一旦混淆调试时会非常痛苦。2.2 空安全如何影响算法编写Kotlin的空安全特性在链表题里是一把双刃剑。好处是它逼着你思考每个引用是否可能为空坏处是如果你不熟悉?.、?:、!!这些操作符的语义写出来的代码容易充满!!反而更难读。我见过不少候选人写Kotlin链表题全程!!看着像Java代码硬翻译过来的。比如var current head while (current ! null) { val next current.next!! // ... }这里的!!完全没必要。current.next的类型已经是ListNode?在current非空的分支里直接赋值给val next current.next就可以编译器会做智能转换根本不需要!!。如果next可能为空那就应该让它的类型保持ListNode?而不是用!!强行断言非空。还有一个常用的技巧用while循环加可空条件判断var curr: ListNode? head while (curr ! null) { // 在这里 curr 已经被智能转换为非空类型 val nextNode curr.next // ... curr nextNode }注意这里如果把curr.next赋值给一个局部变量nextNode再更新curr就不会触发编译器对curr可变性的投诉。因为curr是一个var变量智能转换在它被重新赋值之后会失效但局部变量不会受这个影响。这个小细节能帮你避免很多编译报错。3. 反转链表从迭代到递归的完整推导3.1 迭代法的指针演化过程反转链表的迭代写法是链表面试的第一道坎。很多人的误区在于试图一次跳两步或者想着把整条链“倒过来”。实际上核心操作只有一行curr.next prev。先看标准实现fun reverseList(head: ListNode?): ListNode? { var prev: ListNode? null var curr head while (curr ! null) { val nextTemp curr.next // 保存下一个节点防止断链 curr.next prev // 反转当前节点的指针 prev curr // prev 前移 curr nextTemp // curr 前移 } return prev }这段代码的灵魂是nextTemp。为什么必须先用一个临时变量保存curr.next因为当执行curr.next prev之后curr原来的下一个节点就再也找不到了——链表是单向的你没有回头路。这就像一个在单向通道里行走的人转个身就看不到身后的路标。建议自己在纸上画一下每轮循环的三个节点状态。初始时prev nullcurr指向头节点。第一轮结束后头节点的next指向null它变成了新的尾节点。第二轮结束后第二个节点的next指向第一个节点。依次推进到curr为空时prev正好停在原链表的尾节点也就是反转后的新头节点。这里有个特别容易踩的坑返回prev而不是返回head。很多人写到最后顺手return head结果返回的是反转后的尾节点整道题直接错掉。时刻记住head这个变量在整个反转过程中一直没变它永远指向原链表的头节点但反转完成后它已经是新的尾部了。3.2 递归法的内存视角递归写法比迭代更短但理解门槛更高fun reverseListRecursive(head: ListNode?): ListNode? { if (head?.next null) return head val newHead reverseListRecursive(head.next) head.next?.next head head.next null return newHead }逐行拆解。递归的终止条件是head null || head.next null也就是链表中只剩一个节点或没有节点时直接返回head。这个节点就是最终的“新头节点”它在递归的每一层都被原封不动地向上传递。关键在递归返回之后的操作。假设当前head指向节点Ahead.next指向节点B。递归调用reverseListRecursive(B)返回的是以B为头节点的一整条反转后的链表这条链表的尾节点恰好就是B因为B是原子链表A-B-...中的第二个节点反转后它变成尾节点。所以head.next?.next head的意思就是让B的next指向A。接着head.next null把A原来的下一个指针断掉防止成环。画个三层链表就能看明白。1-2-3递归到最深层时函数处理节点3返回3。回到处理节点2的那一层head是2head.next是3执行3.next 2此时链表变成1-2-32.next还是3。再执行2.next null2和3之间就只剩下3-2这一条边。再回到最外层head是1head.next是2执行2.next 11.next null完成反转。递归写法的代码量确实少但面试时如果决定用递归一定要能说清楚“递归返回的newHead是原链表尾节点”这个关键点同时讲清楚为什么需要head.next null。说不清楚的话面试官很容易怀疑你只是背了模板。3.3 复杂度与边界条件两种写法的时间复杂度都是O(n)空间复杂度有区别迭代法是O(1)只用了两个额外变量递归法是O(n)因为递归调用栈的深度等于链表长度。边界条件一定要主动提不管面试官有没有问。空链表head就是null两种写法都直接返回null。单节点链表head.next是null终止条件命中返回head本身正确。这两个边界在代码里都被终止条件覆盖了但面试时说出来会显得你考虑问题全面。还有一个不太常见但很有价值的边界超长链表。如果链表有上万个节点递归法可能会栈溢出。Kotlin/JVM默认栈大小大约512KB到1MB每个递归帧消耗几十字节链表过长时风险确实存在。所以如果你知道链表的规模可能很大迭代法是更稳妥的选择。面试时可以提一句“递归法在链表过长时有栈溢出风险所以我更倾向迭代实现”这能体现工程意识。4. 反转题的变体家族面试官的层层加码4.1 区间反转基础反转熟练之后面试官常见的加码方式是给你一个区间[left, right]只反转这个区间内的节点区间外的部分保持原样。先上代码fun reverseBetween(head: ListNode?, left: Int, right: Int): ListNode? { val dummy ListNode(0) dummy.next head var prev: ListNode? dummy repeat(left - 1) { prev prev?.next } val start prev?.next var curr start repeat(right - left) { val next curr?.next curr?.next next?.next next?.next prev?.next prev?.next next } return dummy.next }这里有几个关键设计。为什么要dummy节点因为如果left 1反转区间从头节点开始新的头节点会变成原区间内的最后一个节点直接返回head就错了。dummy是一个哨兵节点它的next最终指向正确的头节点这样无论反转从哪里开始return dummy.next都稳。循环里的操作是头插法逻辑。prev始终指向区间前一个节点也就是“反转后新区间头节点”的定位锚点。每轮循环把curr.next这个节点摘出来插到prev后面同时让curr的next跳过它。这个过程重复right - left次正好把区间内的所有节点顺序颠倒。举个例子1-2-3-4-5left2right4。初始prev指向1curr指向2。第一轮把3摘出来插到1后面链表变成1-3-2-4-5此时prev还是1curr还是2。第二轮把4摘出来插到1后面变成1-4-3-2-5。完成正好反转了2、3、4三个节点。这里我踩过一个坑循环次数写成repeat(right - left 1)。多执行一次就会把最终应该作为区间头部的节点也摘掉导致整个链表结构错乱。反转区间内节点的操作次数应该是right - left不是区间长度这个要反复确认。4.2 K个一组反转K个一组反转是区间反转的进阶版也是大厂面试中高频出现的hard题。题目要求每K个节点一组反转不足K个的部分保持原样。递归加迭代的混合写法比较清晰fun reverseKGroup(head: ListNode?, k: Int): ListNode? { var count 0 var node head while (count k node ! null) { node node.next count } if (count k) return head var prev: ListNode? null var curr head repeat(k) { val next curr?.next curr?.next prev prev curr curr next } head?.next reverseKGroup(curr, k) return prev }思路很简单先数出K个节点不足K个就直接返回head。够K个就反转这一段反转之后原来的head变成这一段的尾部让它递归处理后面的链表。返回的prev是反转后的新头。这个代码不难但有一个地方需要特别留意递归调用reverseKGroup(curr, k)时传的是curr也就是当前K段反转后、剩余部分的新起点。如果传成head就会无限递归。时间和空间复杂度时间O(n)每个节点访问常数次空间O(n/k)递归深度是分组数量但每组内还有K层的迭代整体还是O(n/k)当K比较小的时候可以近似常数。4.3 回文链表的判定回文链表这道题网上讨论很多核心考察点是快慢指针加链表反转。判断一个链表是否是回文最暴力的做法是把值存到数组里再两头比较。面试官一般不会直接否但会追问“能不能用O(1)空间”。标准解法是用快慢指针找到中间节点反转后半部分然后从两头逐步比较。fun isPalindrome(head: ListNode?): Boolean { // 找到中间节点 var slow head var fast head while (fast?.next ! null) { slow slow?.next fast fast.next?.next } // 反转后半部分 var secondHalf reverseList(slow) // 比较前半部分和后半部分 var first head var second secondHalf while (second ! null) { if (first?.value ! second.value) return false first first.next second second.next } return true }快慢指针的移动逻辑slow每次走一步fast每次走两步。当fast到达链表末尾时slow正好在中间。链表长度是奇数时slow停在正中间节点上是偶数时slow停在中间两个节点的右侧。这个微妙的差异会影响反转起点但一般不影响判断结果——中间节点反转后与自身比较值相同不会误判。完整做一遍1-2-3-2-1找到中间节点3反转后半部分得到1-2-3然后从原头节点1开始比较依次比较1和1、2和2到second为空时结束判定为回文。Kotlin里这段代码有个小坑while (fast?.next ! null)里fast?.next在fast null时是null条件判断为假循环自然退出所以不会出现空指针。但如果你写的是while (fast.next ! null)编译器会直接报错因为fast是可空类型。这在Kotlin里反而是好事安全由编译器保障。5. 实操中的坑与调试心得5.1 高频翻车点清单我把链表题里最容易翻车的地方整理成了一张清单每条都是自己踩过或者看别人踩过的真实问题。翻车点典型表现解决办法返回值错误反转后返回了原头节点记住迭代结束时prev才是新头head已成为尾部断链修改next后找不到下一个节点先保存nextTemp再修改引用边界遗漏空链表、单节点链表报空指针循环条件用curr ! null或head?.next null确保覆盖循环次数错误多反转一个节点或少反转一个节点用具体链表走一遍确认次数是right - left而非right - left 1环反转后链表变成循环结构递归反转时记得head.next null断开旧指针混淆值相等和引用相等误用在对象比较上链表节点比较身份用比较值用.value第6条在Kotlin里特别值得强调。在Kotlin中对应的是equals对于默认的ListNode类equals比较的是引用所以和效果一样。但如果你用了data class就变成了值比较两个不同对象只要字段相同就会判等。这是数据结构定义层面的坑比任何算法逻辑都隐蔽。5.2 调试技巧怎么用最简单的方式验证链表题链表题调试起来比数组题麻烦因为链表结构在内存里是分散的断点调试时经常看得头大。我常用的方法是写一个打印函数把整条链按顺序输出成数组形式。fun printList(head: ListNode?) { val result mutableListOfInt() var curr head while (curr ! null) { result.add(curr.value) curr curr.next } println(result.joinToString( - )) }每执行一步关键操作比如每次反转循环结束后调用一下printList就能直观看到当前链表长什么样。这个习惯帮我省掉了大量“肉眼断点”的时间。还有一个检查环的技巧用快慢指针。让slow和fast从头开始走如果链表里有环它们一定会在有限步数内相遇。如果要检查自己的反转代码是否产生了意外的环可以写几行快慢指针逻辑快速验证比肉眼盯着next链靠谱得多。另外建议准备好一个构建链表的工具函数方便测试多组数据。我通常会写fun buildList(vararg values: Int): ListNode? { val dummy ListNode(0) var curr dummy for (v in values) { curr.next ListNode(v) curr curr.next!! } return dummy.next }有了这个函数测试反转、区间反转这类题目一行就能构造出测试用例效率提升非常明显。6. 面试准备策略从会做变成讲清楚6.1 讲解思路与复杂度分析算法题做出来只是第一层面试时能把思路讲清楚才是决胜关键。链表题尤其如此因为它的代码量往往不大难在逻辑链条清晰。我在准备链表题时会强制自己按照固定顺序讲先讲数据结构本身的特点——单向链表只能从头到尾遍历没有回头路所以操作的核心是管理好引用再讲本题的关键难点——反转时如何不丢引用接着讲解法思路——用什么方式遍历、每步让指针做什么最后给出复杂度。以迭代反转链表为例可以这样组织表达定义一个prev初始为null一个curr指向head。每轮循环保存curr.next到临时变量然后把curr.next指向prev再整体前移prev和curr。循环到curr为空时prev就是反转后的新头。时间复杂度O(n)空间O(1)。面试官听到这样的回答第一反应是“这人有清晰的工程思维”。而不是你默默写完了代码他要去一行行读。6.2 一段适合面试现场的顺稿模板针对reverseList这道题我把面试现场的讲解思路整理成了一段话你可以参考着练“这道题我用迭代法。定义两个指针prev表示当前节点反转后应该指向的前驱初始为null因为头节点反转后应该指向空curr从head开始向后遍历。每一轮循环先保存curr.next因为接下来要修改curr.next的指向不保存就断链了。然后让curr.next指向前驱节点prev完成当前节点的反转。接着prev移动到curr的位置curr移动到保存好的下一个节点。直到curr为null说明所有节点都处理完此时prev指向原链表的尾节点也就是新链表的头节点直接返回prev。”这段话里包含了三个信息数据结构特点为什么需要保存next、算法核心指针怎么移动、边界处理为什么返回prev。不需要背理解了自然就会说。我自己的经验是刷题时每做完一题用手机录一段自己讲题的音频回放检查哪里有卡顿、哪里没讲清楚。这个方法听起来有点笨但效果奇好。写代码是思考能力的体现讲代码是表达能力的体现两种能力在面试里缺一不可。反复练几次之后你会发现自己面对任何链表题都能边写边讲了。链表题刷到后面你会发现反转这道基础题真的是整个链表专题的轴心。区间反转是它加边界K个一组反转是它加递归回文链表是它和快慢指针的组合。把反转本身的指针演化彻底想明白其他题目都是套框架的事。面试时话不用多但每一句话都要落在关键点上这道题你练透了后面几道变体只是换层皮罢了。
阅读完成 · 觉得有帮助？
