链表系列面试题基本是每个刷“热题101”的人绕不开的一座山。我参与过的技术面试里几乎每一轮都会碰链表哪怕不问反转链表也会拐弯抹角考个环形链表、合并两个有序链表之类。链表这玩意的代码量不大却能把一个人对指针、引用、递归、边界条件的敏感度一次性试出来。这篇想写清楚链表题到底在考什么、高频题有哪些解法、面试官连环追问时你脑子里应该想什么。内容不整虚的急着复习的可以直接跳到第3节抄模板想系统吃透的从第1节往下看就好。1. 链表系列为什么总被拿来“拷打”1.1 代码量少但信息密度高链表题看起来结构简单每个节点只有一个值和指向下一个节点的引用。可越简单的东西越容易暴露基本功。数组题你可以靠索引、靠库函数也可以靠“先排序再双指针”的套路混过去。链表题不一样它逼着你手动操纵引用一个节点指错了后面全乱。面试官只需要让你写一个反转链表再看你几秒能反应过来要记录后继节点就能判断出你平时到底是真写代码还是背题。更重要的是链表题天然带有大量边界情况空链表、只有一个节点、指针已经走到末尾、要删除的恰好是头节点。这些边界情况如果处理不好代码跑起来就崩。面试官不用写测试用例光看着你写代码时有没有下意识处理空指针水平高低就看出来了。1.2 热题101里的链表题型分布热题101是一份很多人照着刷的在线题库里面的链表题数量虽然不算最多但出现频率非常高。我大概统计过链表相关题目占整个清单的十分之一左右而且这些题往往是其他题的基础。分类下来大致是这样题型典型题目核心考点基础遍历反转链表、两两交换、回文链表指针操作双指针环形链表、相交链表、删除倒数第N个快慢指针合并与排序合并两个有序链表、排序链表归并思想加约束K个一组翻转、链表求和局部处理与重排这份清单帮你把散乱的链表题归了类。你会发现很多题表面不一样底层思路就那几个虚拟头节点、双指针、递归、快慢指针。把这几板斧吃透大多数链表题都能现场推出来。1.3 适合用来考察候选人的哪些能力面试官爱用链表是因为它能在很短的面试时间里同时考察三件事。第一代码基本功。链表操作最忌讳的就是“改着改着把自己绕晕”。能不能清晰地在纸上画出节点之间的箭头变化决定了你能不能写出不丢不落的代码。第二边界意识。链表题几乎每一题都要考虑空链表、单节点、头节点变更。这反映一个人在平时写业务代码时会不会主动防御空指针和异常数据。第三沟通思维。白板面链表题面试官最怕那种埋头狂写不吭声的人。链表操作往往有好几种思路你一边写一边说出你的选择、为什么这样处理反而会让面试官觉得你思路清晰。热题101里的链表题正好适合反复训练这种“边写边讲”的能力。2. 吃透链表的底层套路从指针操作到思维模型2.1 虚拟头节点处理边界条件的万能钥匙链表题里第一个高频套路就是虚拟头节点。很多链表问题会涉及在头部插入节点、删除头节点或者把一个链表重新组织。这时候如果你直接操作原始头节点代码里就会出现大量“如果当前节点是头节点”之类的分支。虚拟头节点的作用是人为造一个不参与业务逻辑的节点让所有节点都拥有前驱节点从而把“头节点”变成普通节点。举个例子删除链表中某个值为 target 的所有节点如果不加虚拟头节点while (head ! null head.val target) { head head.next; }删头节点和删中间节点是两套逻辑。加了 dummy 后就不一样了所有节点都可以用同一套“prev.next prev.next.next”来处理。public ListNode removeElements(ListNode head, int val) { ListNode dummy new ListNode(0); dummy.next head; ListNode prev dummy; while (prev.next ! null) { if (prev.next.val val) { prev.next prev.next.next; } else { prev prev.next; } } return dummy.next; }我在模拟面试里见过太多人因为头节点特殊处理翻车不是忘记更新返回值就是 if else 套得晕头转向。加一个虚拟头节点能帮你把代码写得又直又稳。2.2 双指针解决链表题的半壁江山链表在很多场景下是单链表想回头找只能重头遍历。双指针就是在这种限制下衍生出来的大杀器。第一种是快慢指针。两个指针从同一起点出发一个每次走两步一个每次走一步。它能解决的问题包括判断链表是否有环快指针遇不到慢指针就是无环。找到链表中点快指针到末尾慢指针正好在中点。找到环的入口结合数学推导。第二种是前后指针。先让一个指针走若干步再让两个指针一起走。典型场景是“删除倒数第N个节点”你先让快指针走N步再让快慢指针同步走快指针到末尾时慢指针正好停在倒数第N个节点的前一位。面试时提到双指针不要只说名字要说清楚为什么这么做。比如判断环你用两个指针而不是用一个指针配哈希集合核心是空间复杂度从O(n)降到O(1)。这个点面试官几乎必问。2.3 递归与迭代两种视角的取舍链表天然适合递归因为每个节点后面都“跟着一个更小的链表”。递归代码写得短比如反转链表三行搞定但理解起来有门槛而且调用深度一高就可能有栈溢出的风险。迭代代码长一点但空间复杂度是O(1)跑起来稳。面试时你最好两种都能说清楚然后根据题目要求选一种。我的建议是优先保证能写出迭代解法。因为面试现场环境紧张迭代不容易出错与之相对的你被追问“这样写空间复杂度是多少”时也能自信答出O(1)。如果面试官主动问“有没有递归写法”你再补递归版也不迟。这既是加分项又不会让你在基础解法上卡住。热题101里面有好几道题比如合并两个有序链表、反转链表都可以用两种方式写建议都练熟。3. 高频链表题实操代码模板与细节拆解3.1 反转链表递归和迭代都要会反转链表是所有链表题的地基。它本身常考同时也是很多复杂题的前置知识。先看迭代版public ListNode reverseList(ListNode head) { ListNode prev null; ListNode curr head; while (curr ! null) { ListNode nextTemp curr.next; // 先保存后继 curr.next prev; // 把当前节点的指针指向前驱 prev curr; // 前驱位点后移 curr nextTemp; // 当前位点后移 } return prev; // prev 最后会指向原链表的末尾也就是新链表的头 }这个代码最核心的一步是nextTemp curr.next如果不提前保存后面那个节点等你执行curr.next prev之后原来的后继节点就找不到了。很多写错这道题的人都是没意识到“链表指针一旦改变方向后面的路径就丢了”。递归版代码更短但思考方式不一样public ListNode reverseList(ListNode head) { if (head null || head.next null) { return head; } ListNode newHead reverseList(head.next); head.next.next head; head.next null; return newHead; }递归版的思想是先反转当前节点之后的链表最后再处理当前节点。面试时如果写递归一定要解释清楚head.next.next head这步是在让原来的后继节点反向指向当前节点同时把head.next置为 null避免形成环。3.2 合并两个有序链表归并思想的链表版合并两个有序链表本质上是归并排序在链表场景下的局部操作。题目很简单两个链表都已经升序排列你要把它们合成一个有序链表。迭代版可以借助虚拟头节点省去判断谁当头的麻烦public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy new ListNode(0); ListNode cur dummy; while (l1 ! null l2 ! null) { if (l1.val l2.val) { cur.next l1; l1 l1.next; } else { cur.next l2; l2 l2.next; } cur cur.next; } cur.next l1 ! null ? l1 : l2; return dummy.next; }很多人会漏掉 while 循环结束之后其中一个链表还剩下一截的情况。这题的边界就是最后那行cur.next l1 ! null ? l1 : l2必须直接接上剩余链表而不是再写个循环去逐个遍历。因为两个链表都已经有序剩下那一截本来就是排好的直接拼过去就行。这题还有个常见变形是合并 K 个有序链表。虽然热题101里不一定算链表分类但原理是一模一样的只是从两两合并变成了多路归并通常用优先队列维护每个链表当前的最小节点。3.3 环形链表与环入口快慢指针的数学原理判断链表有没有环经典解法是快慢指针。快指针每次走两步慢指针每次走一步如果两个指针相遇说明链表有环。public boolean hasCycle(ListNode head) { if (head null || head.next null) return false; ListNode slow head; ListNode fast head.next; while (fast ! null fast.next ! null) { if (slow fast) return true; slow slow.next; fast fast.next.next; } return false; }这里注意fast head.next是另一种初始化方式两个指针从不同位置出发判断条件稍作调整。核心是如果链表有环快指针迟早会在环里追到慢指针。进阶题是找环的入口。除了判断有没有环还要返回环开始的位置。做法是两个指针从 head 同一起点出发快指针每次走两步慢指针每次走一步第一次相遇后让慢指针留在原地再找一个新指针从 head 出发两个指针每次都走一步再次相遇的位置就是环入口。为什么呢设头节点到环入口的距离为 a环入口到相遇点距离为 b相遇点绕回环入口的距离为 c。慢指针走 ab 步时快指针走 abcb 步。因为快指针速度是慢指针两倍所以 abcb 2(ab)整理得到 c a。也就是说从相遇点继续走 c 步到达入口从头节点走 a 步也到达入口。两个指针同步走便会在入口重叠。这个推导面试时经常被要求讲建议自己画一遍图比背结论靠谱。这题还有一个变体是“返回链表倒数第K个节点”也是快慢指针原理类似但不需要环数学。3.4 删除链表倒数第N个节点一次遍历的优雅解法删除倒数第N个节点最笨的办法是先遍历一遍算长度再走第二遍删除。面试官如果问能不能一次遍历解决你就要用前后指针。思路让一个指针先走 N 步然后两个指针一起走当前面的指针走到末尾时后面的指针恰好停在要删除节点的前驱上。public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy new ListNode(0); dummy.next head; ListNode first dummy; ListNode second dummy; // 第一个指针先走 n 1 步 for (int i 0; i n; i) { first first.next; } // 两个指针同步走 while (first ! null) { first first.next; second second.next; } // second 现在指向待删除节点的前一个节点 second.next second.next.next; return dummy.next; }这里有几个细节容易出错。第一为什么第一个指针要走到 dummy 开始走 n1 步因为 second 初始也指向 dummy等 first 走到 null 时second 正好停在待删除节点的前一位。如果第一个指针只走 n 步second 会指向待删除节点本身无法通过second.next second.next.next删除它。第二为什么需要 dummy如果链表长度正好等于 n即要删除头节点不加 dummy 的话你的 second 会指到 null 附近代码立刻崩。加了 dummy整个删除逻辑统一处理最后返回dummy.next即可。3.5 相交链表让两条链表“对齐”的巧妙思路相交链表这道题要求判断两个链表是否相交并返回相交节点。粗看很容易陷入“双循环”的暴力解法但更优的做法是用双指针走完对方的路。设链表A长度为 L1链表B长度为 L2公共部分长度为 M。两个指针分别从 A 和 B 的头节点出发。指针1 走完 A 后跳到 B 的头节点指针2 走完 B 后跳到 A 的头节点。它们会在第二个遍历轮次里同时进入公共部分如果相交必然相遇如果没相交它们会同时到达 null。public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode pA headA; ListNode pB headB; while (pA ! pB) { pA pA null ? headB : pA.next; pB pB null ? headA : pB.next; } return pA; }这个代码很短但背后的“消除长度差”思想很值得学习。面试时不光要写出来还要能说清楚两个指针走过的总路程分别是 L1ML2 和 L2ML1总路程相同所以会碰到。4. 面试现场怎样接住技术总监的连环追问4.1 一定要先确认边界条件很多候选人拿到链表题就开始写这是大忌。面试官说“反转一个链表”你要立刻反问“这个链表可能为空吗只有单个节点怎么处理函数的返回值定义是什么”这看起来像是在拖延其实是职业习惯。面试官最怕遇到那种写代码不考虑入参是否合法的人。链表题尤其明显因为空链表和单节点是两个必须单独聊的边界。你先确认这些后面写代码就稳了。我见过一个候选人删除链表倒数第N个节点时上来就写主逻辑结果没注意到 n 可以等于链表长度删除头节点时直接空指针。他后来被追问“边界情况想了吗”自己也很懊恼。代码写对一半不严谨的印象已经留下了。4.2 复杂度分析不能只说“O(n)”链表题必问时间复杂度和空间复杂度但“O(n)”太敷衍。面试官想听的是时间复杂度的推导过程。空间复杂度是 O(1) 还是 O(n)为什么。有没有可能用更差或者更好的解法。以删除倒数第N个节点为例如果你上来就说“O(n)因为遍历链表一遍”这是合格的。但更好的回答是“用两次遍历解法是O(n)时间、O(1)空间用双指针一次遍历同样是O(n)时间、O(1)空间但避免了第一遍先算长度实际编码时更简洁。”再说环形链表如果你用哈希集合做空间复杂度是O(n)用快慢指针做空间复杂度是O(1)。面试官喜欢看到你有对比意识并能解释空间换时间或时间换空间这种经典 trade-off。4.3 白板写码的细节与习惯白板写码和 IDE 里写码完全不一样。IDE 有自动补全和即时报错白板没有所以书写习惯和命名习惯都会被放大。我的建议是在白板或在线模拟面上先用注释把关键步骤写出来再填代码。比如// 1. 先处理空链表 // 2. 加虚拟头节点 // 3. 使用双指针定位前驱这能让你在写的过程中不迷失方向也让面试官看到你的思路。代码里的变量名也要起得直观prev、curr、dummy这些几乎已经成为共识尽量别用a、b、c。一旦用完解释代码时要多花三倍时间。还有一个细节指针操作完一定要手动画一下链表的箭头示意图或者至少在心里模拟一次。如果在白板上写可以用手指比划一下“现在这个节点的 next 指向哪里”防止写串。5. 常见问题与避坑实录5.1 空指针和悬空引用链表题最常见的错误就是空指针。你访问了node.next但 node 为 null或者你构建了一个环后遍历时永远出不来。应对空指针要养成“访问 next 前先确认当前节点非空”的习惯。这个习惯可以通过刷题练出来每写完一步指针操作回看一眼这一行操作的变量在上一轮循环里是否被正确赋值。更隐蔽的是悬空引用。比如删除一个节点后如果还有别的指针指向这个被删除的节点后续走这个指针就会拿到一个丢失的节点。恢复现场时尤其要小心。我刷题时有个习惯每道链表题写完都拿三组用例跑一遍空链表、单节点链表、普通多节点链表。跑到第三组时很多隐藏 bug 就出来了。5.2 递归带来的栈溢出递归写法看着简单但链表一长调用栈就长。面试官问“如果链表节点有十万个你的递归能跑吗”就是想考你递归栈溢出的问题。大多数链表递归题的时间复杂度是O(n)但空间复杂度也是O(n)因为在递归过程中每一层调用都占用栈空间。如果你追求空间上的稳定应该用迭代。我的建议是面试时先把迭代解法讲清楚再补充递归解法。如果只想写一种我建议写迭代。不是递归不重要而是面试现场更需要稳。5.3 倒数第N个节点的越界问题删除倒数第N个节点如果 N 大于链表长度怎么办正规题目一般约定 N 是合法的但面试官会问你这个约定。如果你选择的解法是“先遍历一遍算长度再删除正数第 length-n1 个节点”那么就需要先判断n length否则会得到一个负数索引程序报错。如果你用双指针的解法第一个指针走 n1 步时如果链表提前结束说明 n 超出范围也要处理。但更推荐的做法是在开篇就向面试官确认“题目是否保证 N 合法”如果保证你就不用写防御代码如果不保证再补上判断。这种确认本身就是面试表现的一部分。5.4 题目变形两两交换、K个一组翻转、回文链表热题101里链表题还有一些变形比如每两个节点交换位置、K个一组翻转链表、判断链表是否回文。这些题看着新实际套路还是那几个。两两交换相邻节点核心是用虚拟头节点然后三个指针一起操作prev、cur、next。因为要调换 cur 和 next 的位置必须保存 next 的 next不然换完就断链。K个一组翻转链表是反转链表的扩展版。先确定这一组有没有 K 个节点有就局部反转反转完接回到原来的链上。这里比普通反转多出的关键点是每一组反转后要跟前一组尾部接上后一组开头接上所以需要递归或循环控制。判断回文链表更直接的做法是把链表后半段反转然后从两头开始比较。这里需要先找到中点恰好用前面说的快慢指针。一个问题把找中点、反转、比较三个知识点全考了。这些变形题不建议死背代码先画图把每一步的指针状态画出来代码自然就写出来了。6. 我的一点体会链表题是我见过的“刷题性价比”最高的模块之一。它翻来覆去就那几种套路一旦想通了很多题看着都会眼熟。我最大的感受是不要在一道题上一遍遍抄答案而是要把每个指针操作的意图想透。如果你也想吃透这份热题101里的链表题我建议从今天开始给自己订一个规则每刷完一道题不看题解独立把代码再默写一遍然后口述一遍解题思路。能讲清楚才是真会。面试时真正丢分的人往往不是不会写而是写完之后说不出为什么这么写。链表题恰恰是面试官最喜欢追问“为什么”的考点所以每一次刷题都当作模拟面试来对待。
