★ FEATURED ARTICLE 我前一阵密集面了几家公司发现一个挺有意思的现象不管面试官是什么级别、什么方向链表题几乎成了“标配开场”。尤其是准备过牛客面试热题101里链表系列之后很多题你甚至不用等面试官开口心里已经能预判他要考你哪个变体。这份题库的妙处在于——它不是堆题而是把链表能考的点全给串起来了。这篇文章我就以“面试拷打技术总监”的视角把链表系列从头到尾拆一遍。不只是给答案而是把为什么这么写、面试官想听到什么、实践里哪些坑最致命全讲清楚。准备校招社招、转码刷题的朋友这篇可以直接当作链表模块的复习提纲。1. 链表在算法面试中的位置它到底在考你什么很多刷题新人会低估链表。觉得不就是节点 next 指针嘛比数组难不到哪去。实际上链表题是面试里性价比极高的一类题原因在于它同时考察了三件事。第一是代码基本功。链表题没有现成的库函数能绕过去每一步都是裸的指针/引用操作写不写得干净利落、会不会多写空指针判断、断链之后还记不记得接回去基本上一眼就能看出来有没有工程底子。第二是边界条件意识。空链表、只有一个节点、两个节点、头尾删除、环的存在这些边界在链表题里是高频考察点。面试官往往不会直接提醒你他会在你写完代码后追问一句“如果链表只有一个节点呢如果 k 等于链表长度呢”答不答得上来直接决定了这题的评级。第三是抽象建模能力。链表题里有相当一部分不是单纯考遍历比如快慢指针、链表相加、合并 K 个排序链表这些题本质是在考你能不能把一个复杂问题拆成简单的子问题或者识别出某些题其实是双指针/归并模式的变体。我面试的时候有个体会面试官其实不太在意这道题你以前做没做过他在意的是你有没有形成一套稳定的解题方法论。做准备要做到底层逻辑层面而不是背题。1.1 为什么我建议把 101 里的链表题当“模块”刷刚开始刷题容易陷入一个误区——按题号顺序刷今天刷到链表就刷链表明天跳到二叉树就接着做。这样刷到后面会有一个严重的副作用知识点是散的面试时调用不出来。我的做法是把链表系列拆成几个子模块每个模块对应一种核心技法基础操作与虚拟头节点覆盖删除类、插入类题目反转与穿针引线覆盖从整体反转、区间反转到 K 个一组反转快慢指针与环覆盖判环、环入口、倒数节点、找中点排序与合并覆盖合并有序链表、K 路归并、链表排序综合模拟覆盖链表相加、重排链表这类需要边分析边处理的问题。每个子模块集中刷 5 到 8 道题刷完你会立刻发现题目之间是互通的很多题的核心就一两行代码剩下全是边界处理。1.2 面试官真正期待的能力模型曾经有位面试官直接跟我说过一句话链表题写到后面判断一个人的水平不是看他能不能 AC而是看他遇到“删除某个节点但只给你这个节点本身”这种问题时的第一反应。这其实是在说你有没有养成“拿不到前驱就创造前驱”的思维习惯。这就是为什么虚拟头节点在链表题里这么重要。它本质上是一个“桩子”帮你把特殊位置头部变成普通位置代码逻辑就统一了。这种在面对边界场景时主动加缓冲层的意识放到工程里其实就是防御式编程。所以每次答链表题我脑子里会过一遍这里有几种边界哪些边界用统一的技巧能消化掉时间复杂度是否仍是最优这三个问题答完基本就不用担心面试官再刁难。2. 三个必会的链表底层技能堆出所有解法的地基链表题的花样再多底层靠的还是那三板斧。把这三样练到肌肉记忆剩下就是识别题型套框架。2.1 虚拟头节点让头部删除不再特殊先看一个最简单的例子删除单链表中等于给定值的所有节点。如果不用虚拟头节点你得先写一个 while 循环把开头的连续命中节点删掉再处理中间部分。但如果带一个 dummy 头节点代码就变成同一套逻辑不会有任何位置分支def removeElements(head, val): dummy ListNode(0) dummy.next head pre, cur dummy, head while cur: if cur.val val: pre.next cur.next else: pre cur cur cur.next return dummy.next这个套路几乎贯穿整个 101 链表模块删除链表的倒数第 N 个节点、删除排序链表中的重复元素、移除链表元素都能用 dummy 把开头位置的“特殊性”抹平。你只需要记住一句口诀不确定头节点会不会变就加一个虚拟头节点。2.2 三指针状态保持移动顺序是唯一难点链表的很多操作本质上是在维护一个“滑动窗口”。反转一个链表时维护 pre、cur、next 三个指针判断环时维护 slow、fast 两个指针删除倒数第 N 个时维护 first、second 两个指针。指针本身的定义不难难的永远是指针移动的先后顺序。打个比方这就像你在挪动一串手链上的珠子你要把某个珠子换到别的位置必须先松开前后两颗珠子的连接然后把目标珠子取出来再接到新位置。如果顺序错了要么手链散架丢失链表后半段要么你自己都搞不清珠子是哪颗指针错乱。所以我每次写链表题都会遵守一条铁律修改任何节点的 next 之前先把它的下一个节点用临时变量保存下来。我可以这样告诉你所有链表题报错“运行超时”或“访问了空指针”八成都是断链之后找不回来了。2.3 画图是列公式不是浪费时间面试或者自己刷题时遇到稍微绕一点的题我建议直接在白板上画链表节点之间的指向变化。不要只用脑推画出来之后代码就是照着图写的。这个能力是可以刻意训练的。我刷 101 链表系列的时候每道题都要求自己只对着图写代码。一开始画得很慢后来发现这套视觉化的工作流优势很大——脑子不需要同时 hold 住“现在的状态”和“下一步要做什么”画完图代码自然就出来了。面试时还有个小技巧如果你需要在白板上画图面试官不但不会不耐烦反而会认为你的解题方式可验证、可沟通属于加分项。3. 反转系列从迭代到递归把“穿针引线”想明白反转链表是 101 链表系列里出现率肉眼可见高的题型。光一个整体反转就有迭代、递归两种写法再往上加区间、按组翻转、两两交换难度也会随之上升。但核心只有一条主线段内反转的本质是逐个把节点挪到头部。3.1 整体反转的迭代与递归实现暴力解法就不提了看迭代版。维护 pre、cur 两个指针不断让 cur.next 指向 pre然后整体右移def reverseList(head): pre None cur head while cur: nxt cur.next # 保存后继防止断链 cur.next pre # 反转指向 pre cur cur nxt return pre递归版会稍微烧脑一点。核心思路是把“反转整个链表”转化为“反转 head.next 这个子链表再把 head 接到末尾”def reverseList(head): if not head or not head.next: return head new_head reverseList(head.next) head.next.next head head.next None return new_head面试时我更推荐先说迭代版因为好解释、不会栈溢出。如果面试官追问“能不能用递归”再补充递归版本并说明递归会把大量栈帧压栈链表太长有风险。3.2 区间反转与 K 个一组反转的通用框架区间反转反转从 left 到 right 的部分比较通用的写法是先找到 left 的前驱节点然后在这个区间内重复执行“头插法”。所谓头插法就是每次把当前节点拎出来插入到区间头部之后def reverseBetween(head, left, right): dummy ListNode(0) dummy.next 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.nextK 个一组反转只是把区间反转重复多遍每轮找到第 K 个节点然后套头插法。注意两点一是 K 可能大于剩余长度需要边数边处理二是反转完一组后pre 要移动到新的组头。3.3 反转类题目最容易踩的坑反转类题目我在实际写的时候踩过两次坑。第一次是忘记把最后一段内部链接翻转完后末尾接上新组头。其实这对应代码里 pre.next 的更新顺序顺序不对就会接错。第二次是“区间反转”时把 cur 和 nxt 搞混导致链表成环。面试时这种成环错误特别致命——代码不会报错但跑测试会直接超时。我的调试经验是遇到反转类题就打印整个链表看看每个节点的 next 是不是和预期一致。比如打印 [1,2,3,4,5] 反转后变成 [5,4,3,2,1]每个节点的数值和顺序都能对上的话基本就稳了。4. 快慢指针环、倒数 K、交点三兄弟一次打尽快慢指针是链表模块里最值得深挖的一类题。它表面是对两个指针速度的控制实际上背后是一套数学关系。把数学关系想清楚环形链表、环形链表入口、链表中倒数第 K 个节点、相交链表就全部变成同一类题的变体。4.1 判断链表是否有环为什么快指针至少要快一步判断环的经典做法是快指针每次走两步慢指针每次走一步。如果存在环两指针必然相遇。有人会问为什么快指针不走三步、四步因为步幅太大有风险比如链表很长但环很小快指针可能反复跳过慢指针所在位置在环内跳格子导致迟迟不相遇。步幅差为 1 时最多走 O(n) 轮必然相遇是最稳妥的。def hasCycle(head): slow fast head while fast and fast.next: slow slow.next # 慢指针走一步 fast fast.next.next # 快指针走两步 if slow is fast: return True return False4.2 找环形入口位置记下一个等量关系进阶题是不仅要判断有环还要找到环的入口。这题网上推导很多这里给一个便于记忆的结论。设链表头到环入口的距离为 a入口到相遇点的距离为 b相遇点到下一次回到入口的距离为 c。当快慢指针相遇时慢指针走了 ab快指针走了 ab n*(bc)。因为快指针行程是慢指针的两倍可以推出 a c (n-1)*(bc)。这个式子翻译成人话就是从相遇点开始走和一个从头节点出发的新指针同步走两者会在环入口相遇。代码实现很直接def detectCycle(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: ptr head while ptr is not slow: ptr ptr.next slow slow.next return ptr return None当初刷到这里的时候我还特意画了一堆图去验证结论。面试的时候如果有人追问“为什么是走两步而不是走一步”能把上面的等量关系讲清楚会显得你确实吃透了原理而不是背了模板。4.3 倒数第 K 个节点与相交链表找链表的倒数第 K 个节点用一个快指针先走 K 步然后快慢同步走快指针到底时慢指针正好指向倒数第 Kdef getKthFromEnd(head, k): fast slow head for _ in range(k): if not fast: return None fast fast.next while fast: fast fast.next slow slow.next return slow相交链表题的思路稍微需要变通一下让两个指针分别从 A、B 头出发走到结尾后切换到对方链表继续走。如果两个链表有交点两个指针必定会在交点相遇如果没有交点它们会同时走到 None。这个思路本质是让两个指针走过相同长度。这几个题掌握之后快慢指针类题的规律就清楚了先想清楚谁先走、速度差多少再想清楚相遇之后要利用哪个等量关系。5. 删除、排序与合并高频中等题的重灾区如果说反转和快慢指针是热身那删除、排序、合并这几类题才是回回卡人的地方。它们不像反转那么“公式化”每题都需要结合具体场景设计细节非常考验边界处理。5.1 删除链表的倒数第 N 个节点虚拟头节点加双指针的标准配合这题是快慢指针和 dummy 节点的组合应用。先让 first 走 N 步然后 first 和 second 同步走first 到尾时 second 正好指向待删节点的前一个节点。因为涉及删除头部的情况直接给链表加一个虚拟头节点最稳妥def removeNthFromEnd(head, n): dummy ListNode(0) dummy.next head first head for _ in range(n): first first.next second dummy while first: first first.next second second.next second.next second.next.next return dummy.next注意一个细节这里 second 初始化为 dummy而不是 head。这样能保证 first 到底时second 指向“待删节点”的前驱。如果把 second 初始化为 head遇到删除头节点的情况就会漏掉该有的处理。5.2 合并两个有序链表与合并 K 个排序链表两个有序链表合并是归并排序的雏形。迭代版用一个哨兵头节点维护结果链表的尾部指针递归版更短但要注意递归深度def mergeTwoLists(l1, l2): dummy ListNode(0) tail dummy while l1 and l2: if l1.val l2.val: tail.next l1 l1 l1.next else: tail.next l2 l2 l2.next tail tail.next tail.next l1 or l2 return dummy.next合并 K 个排序链表常见思路有三种两两合并、优先队列逐步取最小、分治归并。我推荐优先队列的实现代码直观且时间效率稳定。面试时你可以先把两种思路都说出来再选自己熟悉的那版写这样会让面试官觉得你是在做方案选型而不是死记硬背。5.3 链表排序归并排序的“找中点 合并”组合拳单链表排序不能像数组那样随便随机访问所以最好写的排序算法是归并排序。步骤就三步用快慢指针找链表中点递归排序左右两段用上面的 mergeTwoLists 合并。中点注意用 fast 和 fast.next 同时判空否则会取不到正确的左半部分。写完后跑一个 5 个节点的奇数长度和一个 4 个节点的偶数长度用例基本就能确认没问题。5.4 链表相加进位处理的两种方向链表相加有两种变体正序相加和逆序相加。逆序数字低位在前比较好处理直接同时遍历两条链表维护进位即可。但正序相加时数字的低位在链表尾部此时可以先把两条链表反转再按逆序相加最后把结果反转回来。这个思路本身不难难的是你当场能不能意识到“反转一下就能把问题转化成熟悉的形态”。所以平时刷题我养成了一个习惯遇到不顺手的题目先想想能不能通过一次反转、加虚拟头、或者双指针把它变成做过的题。这一招在面试当场非常救命。6. 综合题与易错点面试场上最怕的翻车现场刷完上面几大模块后基本能做到 101 链表系列里的题一眼有思路但离“面试不翻车”还有一段距离。我觉得最后一段必须单独聊聊面试现场的真实情况以及怎么在实战中稳定发挥。6.1 成环死循环的典型场景与快速排查链表题最常见的严重错误就是成环——不是因为链表本身有环而是你在反转、删除、重排的过程中把 next 指错了造成循环。这种错误最迷惑的地方在于程序不报错但测试时会超时。我自己就有一次在“重排链表”这道题上把 pre.next 和 cur.next 接反了代码跑起来直接死循环。当时完全没想到是逻辑问题还以为是编译器卡了。排查方法很老套但有效不要直接盲试先打印整个链表每次操作后的状态。用 Python 的话可以写一个辅助打印函数每次修改完链表就打印一遍。链表的节点数一般不大打印成本完全能接受。6.2 递归深度和栈溢出不是所有链表题都适合递归链表题里很多经典解法都有递归版本比如反转链表、合并有序链表、归并排序。但面试时要多考虑一层如果这是一个几万节点的超长链表递归会怎样递归版本会占用 O(n) 的调用栈。面试官如果问“如果链表非常长你的解法还适用吗”其实就是在考察你有没有意识到栈溢出风险。我的习惯是先说清楚递归版是一种优雅的写法然后主动补充迭代版作为短链表的稳妥选择。不光是链表任何递归题我都很认可“先讲清楚两种方案的取舍”的表达方式。这是高级工程师跟初级开发拉开差距的地方。6.3 面试表达从“会写代码”到“讲清楚方案”代码写对了并不代表面试分数一定高。我面过的所有公司里那些给出高评价的候选人共同点是都能用很清晰的逻辑把自己的解题过程讲出来而不是闷头写完让面试官自己看。链表题我建议按这个顺序组织表达先说出题型的核心模式比如“这题是快慢指针 虚拟头节点的典型应用”再分析关键边界比如删除头部、链表长度为 1、k 大于链表长度然后写代码边写边解释每个关键赋值动作的目的最后主动分析时间复杂度和空间复杂度。这套表达框架其实也是在向面试官展示工程能力面对一个需求你懂得先梳理方案、再处理边界、最后落地实现。6.4 我练完 101 链表系列后的做题感受最后说一点个人体会。刚刷链表题的时候我最容易陷入“对着答案抄一遍就觉得自己会了”的假状态。后来我换了个策略每天只刷 3 道链表题但每道题必须做到三遍。第一遍不看代码自己试着写第二遍对答案分析差距第三遍在完全不看笔记的情况下重新实现并加上边界测试用例。这种方法比较笨但坚持下来之后链表题在面试里基本不会再让我恐慌。而且练到后期你会发现自己真的能跟面试官聊出些门道来——他抛一个变体你就能大概猜到他想听哪个思路。所谓“拷打技术总监”其实就是把这道题的所有角度都提前想过一遍等他开口提问时你已经有备而来。
阅读完成 · 觉得有帮助？
