聊链表面试题总有读者让我把牛客和力扣那套必刷101榜单里关于链表的题单独拎出来讲透。这次我直接把压箱底的笔记整理出来一份2万行源码加注释的仓库前后刷了三轮每一道题都用手写过、用测试用例砸过才算把链表这个“看似简单、实则全是细节”的题型吃进肚子里。这篇博文就是那份笔记的精华版不聊虚的只讲面试现场真正会被拷打的东西。先说结论链表在面试里的地位很特殊。它不像动态规划那样烧脑也不像系统设计那样需要广博的工程经验但它几乎是所有大厂手撕算法环节里出现频率最高的题型之一。原因很简单——链表题能同时考察你对指针/引用的理解、对边界条件的敏感度、对空间复杂度的控制力以及最重要的你写代码时有没有防御性思维。很多开发者刷了上百道题觉得自己“会链表”但面试官问一句“如果链表有环会怎样”瞬间就露怯。所以这次我们不追求题目数量追求的是把链表题的底层逻辑和面试官的出题心理都摸透。这份笔记覆盖了必刷101榜单里所有链表题我把它们按题型重新归类每类提炼出统一的解题框架再配上手写源码和逐行注释。下面按四个维度拆解先讲清楚链表题考察的本质再给高频题型分类和模板然后逐题拆解三道最经典的题目最后把源码调试和面试现场的经验一并奉上。1. 链表到底在考什么先把底层逻辑吃透1.1 为什么链表题能成为面试“必刷”题型我从面试官的角度来说。候选人的简历上几乎人人都写“熟悉数据结构与算法”但链表题是少数能让这种模糊表述立刻现出原形的考察点。数组、哈希表这些数据结构即使理解不深套模板也能写出像样的代码但链表题不一样它要求你精确地操作一个个节点之间的指针关系。一个指针指错了整个链表就断了一个边界没考虑到循环就死转或报空指针异常。这种“容错率极低”的特性恰好能区分出“背过题”和“真会了”两种候选人。另外一个现实因素是链表题非常适合用来考察工程素养。面试官可以顺藤摸瓜地问出很多细节——比如“这个题如果用递归空间复杂度是多少”“为什么这里要用虚拟头节点”“能不能不用额外空间”这一连串追问本质上是在验证你有没有真正的代码感觉而不只是背答案。从数据结构本身来看链表是理解更复杂数据结构的基础。LRU缓存、跳表、Redis底层链表结构、文件系统里很多索引结构都和链表思想相关。面到后面的系统设计轮链表相关的设计题也不少见。所以刷链表题不只是为了应付算法轮它本身就是一种底层功力的储备。1.2 指针操作的“人话”理解pre、cur、next三指针思维模型很多初学者学链表最大的障碍是一堆指针指来指去画图画了半天代码一写就懵。我总结过一个特别有用的思维模型把链表想象成一列火车每个车厢就是一个节点车厢里存着数据车钩就是指向下一个车厢的指针。在绝大多数链表操作里你只需要盯住三样东西pre当前节点的前一个节点也就是“身后的车厢”。cur当前正在处理的节点也就是“你正坐着的这节车厢”。next当前节点的下一个节点也就是“前方的车厢”。任何涉及“断开重连”的操作都遵循一个铁律先接好后面的再动当前的。也就是说先把next保存下来或者先把下一段连接处理好再去修改cur的指针。很多空指针错误就是因为在修改cur-next之前没有保存原来的next导致后面的节点找不到了。拿最经典的反转链表来说。你要把cur-next从指向next改成指向pre。如果不先把next存下来改完之后整个链表后半段就丢了这就是断链。所以正确顺序是先用临时变量tmp保存next再让cur-next pre最后把pre和cur都往后移动一步。这个“先保存、再断开、再重连”的顺序不仅链表题用凡是涉及指针重组的题都用得上。1.3 面试官真正想考察的三层能力第一层是操作能力。你能不能写出基本遍历、插入、删除、反转。这层靠刷题量堆出来刷到100题以上基本没什么问题。第二层是抽象能力。遇到链表类问题能不能快速识别出它的模型。比如判断“倒数第k个节点”本质上是“双指针间距固定为k”判断“链表是否有环”本质上是“追及问题”判断“合并多个有序链表”本质上是“多路归并”。能把这层想清楚的人写代码基本是水到渠成。第三层是边界意识与鲁棒性。空链表、只有一个节点、两个节点、有环的链表、超长链表会不会越界会不会内存泄漏。这层才是面试中拉开差距的关键。同样的题很多人五分钟写完但面试官轻轻一问“如果链表只有一个节点你怎么处理”就有人开始慌了。边界处理恰恰是链表题最容易失分也最值得炫耀的地方。我会在后面详详细细地把每类题的边界场景都列出来。2. 高频题型分类与解题框架把101榜单的链表题切成四大盘先做一道归类。我把牛客和力扣必刷101榜单里所有链表题按考察点和解题模型分成四类。这四类几乎覆盖了榜单里的全部链表题面试遇到的任一新题只要能归入其中一类解法框架基本可以直接套用。题型分类典型题目核心思路时间复杂度空间复杂度反转类反转链表、反转链表II、K个一组翻转链表三指针迭代或递归O(n)O(1)或O(n/k)递归栈环形与交点类环形链表、环形链表II、相交链表快慢指针/哈希表O(n)O(1)或O(n)合并与排序类合并两个有序链表、合并K个有序链表、排序链表双指针/优先队列/归并O(n log k)O(k)或O(log n)删除与定位类删除倒数第N个节点、删除重复节点、找中间节点双指针/哑节点/前缀信息O(n)O(1)2.1 反转类题型记住三指针与递归切换两种姿态反转类题目的核心是“指针重连”。无论是反转整个链表、反转局部区间还是K个一组翻转本质上都是在一个局部范围内重复执行三指针操作。我建议你把基础版的反转链表练成肌肉记忆在纸上画一百遍做到闭着眼睛能写出来后面所有变种都只是在这个基础上加判断条件。要注意的点有两个。第一区间反转时虚拟头节点的作用非常明显。因为一旦要反转的区间从链表的头部开始头节点本身就会变这时候如果不设哑节点你就得单独讨论“头部反转”的情况代码会又长又容易出错。第二K个一组翻转比区间反转多了一个步骤——先数清楚这一组里有没有K个节点不足K个就直接返回。这个“先计数再反转”的操作会让代码多一层循环但也正是这层循环让题目难度从“简单”一跃到“困难”。面试的时候如果写不出K个一组翻转退而求其次写出“每两个节点一组翻转”也能保住印象分。2.2 环形与交点类题型快慢指针是万能钥匙环形链表和相交链表这两类题牛客和力扣上出镜率极高几乎每三场面试就有一场会碰到。它们的共同特征是需要“没有额外空间的条件下完成检测”而这正好是快慢指针的强项。快慢指针的原理我用人话解释一下两个指针同时从头部出发快指针每次走两步慢指针每次走一步。如果链表没有环快指针会率先到达尾部如果有环两个指针就会在环里相遇。这本质上是数学里的追及问题——当慢指针进入环后快指针相对慢指针每次缩短一步距离因为速度差是1所以总会在有限步内追上。相交链表的思路也很有代表性。两个指针分别从两条链表头部出发一旦走到尾部就跳到另一条链表的头部继续走。因为两条链表的总长度差值在“交换走”的过程中被抵消了所以如果它们相交两个指针必然会在交点相遇如果不相交它们会同时到达各自的链表尾部返回空。2.3 合并与排序类题型归并思想贯穿始终合并两个有序链表是很多候选人的“开胃菜”。用递归写只有五行代码但你别高兴太早因为面试官紧接着就会升级成合并K个有序链表这道题一出来至少一半的人会卡住。合并K个有序链表有三种主流解法第一种两两合并顺序执行时间复杂度O(k * n)虽然简单但效率偏低第二种用优先队列维护K个链表的当前头节点每次弹出最小的节点整体时间复杂度降为O(n log k)这也是大多数题解的标准答案第三种分治归并先把K个链表两两配对合并出K/2个再继续合并时间复杂度同样是O(n log k)但不需要额外维护堆结构。面试到这道题的时候我会习惯性追问一句“如果内存非常紧张你会选哪种实现”这是一个典型的空间换时间问题能够考察候选人在不同约束条件下的取舍能力。链表的龟兔赛跑、找中间节点这类题本质上也是归并排序链表的基础你需要先能用快慢指针把链表均匀分成两半才能继续做后续的递归归并——这一连串的知识点都是环环相扣的。2.4 删除与定位类题型哑节点是保命符删除类题目的最大坑点在于当你删除的是头节点时返回的“新头”需要变成原来的第二个节点这让很多人写出的代码被迫大段大段地判断if (head NULL)、if (head-next NULL)。但用虚拟头节点dummy node可以一劳永逸地消掉这些分支判断。方法很简单新建一个节点让它指向head所有操作都在这个虚拟节点后面进行最后直接返回dummy-next即可。删除倒数第N个节点是删除类里的经典题。核心逻辑是“快指针先走N步”然后快慢指针同时前进当快指针走到链表末尾时慢指针的后面一个节点就是我们要删的节点。这个过程只遍历一次时间复杂度O(n)空间复杂度O(1)。删重复节点也是同一个套路用一个指针遍历发现cur-val cur-next-val就连续跳过唯一需要注意的是“删完后要不要保留一个同样的值”——这决定了你代码里几行判断的差别。找中间节点这道题我放在删除类里可能有点怪但它在链表排序和重排中太常用了。快慢指针同时从头出发快指针到尾时慢指针正好在中间对于不确定长度的链表这就是最优雅的定位方式。3. 三题定乾坤最常考的三道链表面试题逐个拆解榜单里的链表题说多不多说少不少刷到最后会发现很多人只把题目过了一遍却没有把最核心的三道题吃透。这三道题我用真实面试中被追问频繁、案例丰富的程度来排序每一道都会给出源码片段和逐行注释并说清楚面试官每一层追问背后真正的意图。3.1 反转链表I与II迭代三指针与递归两种视角先来看最简单版本的反转链表。我的建议是两种写法都会因为面试官经常让人“换种写法”。迭代三指针是默认答案递归则能展示你对递归栈的理解。// 反转链表迭代法 struct ListNode* reverseList(struct ListNode* head) { struct ListNode* pre NULL; // 前驱节点初始为空 struct ListNode* cur head; // 当前节点从头开始 while (cur) { struct ListNode* next cur-next; // 先保存后继 cur-next pre; // 将当前节点指向前驱核心反转动作 pre cur; // 前驱后移 cur next; // 当前节点后移 } return pre; // 遍历结束后pre就是新的头节点 }递归写法核心在于假设reverseList(head-next)已经把后面一整段都反转好了那现在只需要让head-next-next head也就是让当前节点的后继节点反过来指向自己再把head-next置空就完成了当前节点的反转。递归写法的关键是“信任递归函数已经处理好了后面的部分”思维上非常依赖抽象能力。它的空间复杂度是O(n)因为每一层递归都占一个栈帧面试的时候把这一点主动说出来面试官会认为你考虑很全面。反转链表II要求反转从位置m到n的区间节点这题的难度在于定位和拼接。定位部分用“预先走m-1步”的方式找到目标区间的起点反转部分使用上面的三指针法。有一件特别容易出错的事反转完毕后区间的前驱的next和区间起点的next都要重新接好。这里我贴出核心代码片段struct ListNode* reverseBetween(struct ListNode* head, int m, int n) { struct ListNode dummy; dummy.next head; struct ListNode* pre dummy; for (int i 1; i m; i) { pre pre-next; // pre最终指向反转区间的上一个节点 } struct ListNode* cur pre-next; for (int i m; i n; i) { struct ListNode* next cur-next; // 待搬移节点 cur-next next-next; // 跳过next next-next pre-next; // next搬到区间头部 pre-next next; // 更新区间头 } return dummy.next; }这里使用的是“头插法”每次把后面的一个节点搬到区间开头注意循环次数是n-m次不要习惯性写成n-m1。每次面试我都会遇到有人在这里纠结多写几个测试用例比如m1n链表长度就能确认自己没问题。3.2 环形链表与环形链表II快慢指针相遇之后呢环形链表第一问只问“有没有环”快慢指针在环内相遇即可返回true。这里我建议你手动推导一下为什么快指针走两步而不是走三步如果快指针一次走三步慢指针一次走一步虽然理论上也能追上但要考虑“错过”的情况——速度差越大步长落在节点上的位置就可能越过慢指针导致需要多走好几圈才能相遇。速度差为1是保证“必然在有限步内相遇”的最稳定选择。bool hasCycle(struct ListNode *head) { if (head NULL || head-next NULL) return false; struct ListNode *slow head; struct ListNode *fast head-next; // 先走一步避免循环条件歧义 while (fast ! slow) { if (fast NULL || fast-next NULL) return false; slow slow-next; fast fast-next-next; } return true; }环形链表II更狠要求找环的入口。快慢指针第一次相遇后让一个指针从头重新出发另一个指针从相遇点出发两者每次都走一步再次相遇的那个节点就是环的入口。这个结论看起来玄学实际上有严格的数学推导设链表头到环入口的距离为a环入口到相遇点的距离为b慢指针走的路程是ab快指针走的路程是abk圈又因为快指针速度是慢指针的2倍所以abk圈2(ab)解得a (k-1)圈 (环长度-b)也就是说从头出发的指针走到环入口时从相遇点出发的指针也会到达环入口。面试时能把这个推导说清楚印象分直接拉满。3.3 合并K个有序链表优先队列解法与分治解法的现场取舍合并两个有序链表就不展开贴代码了大家都熟。我直接说合并K个。最容易被面试官追问的点是优先队列方案里的“容量”和“比较器”细节。#include queue struct cmp { bool operator()(ListNode* a, ListNode* b) { return a-val b-val; // 最小堆C优先队列默认最大堆这里反转比较 } }; ListNode* mergeKLists(vectorListNode* lists) { priority_queueListNode*, vectorListNode*, cmp pq; for (ListNode* node : lists) { if (node) pq.push(node); // 每个链表的头节点入堆 } ListNode dummy; ListNode* tail dummy; while (!pq.empty()) { ListNode* minNode pq.top(); pq.pop(); tail-next minNode; // 当前最小节点接到结果链表的尾部 tail tail-next; if (minNode-next) pq.push(minNode-next); // 该链表的下一个节点入堆 } return dummy.next; }复杂度方面优先队列方案每次弹出并插入一个节点堆的操作是O(log k)总共n个节点被处理总复杂度O(n log k)。面试官如果追问“能不能把空间复杂度降到O(1)”你可以回答用分治两两合并每轮合并的代价是O(n)总共合并log k轮时间复杂度同样是O(n log k)但不需要维护大小为k的堆空间上更省。这个环节通常会是技术总监轮特别喜欢的讨论点因为他们更看重候选人能不能在工程约束下做取舍。4. 源码里最容易被忽略的5个细节边界条件与调试心得我在整理这2万行源码的时候逐行加了注释同时也记录了大量“当我没注意边界时踩过的坑”。这一章节直接把这些坑集中曝光每个都配一句“为什么错”和“怎么改”。这些细节在题解里通常只是一笔带过但面试现场等着你踩。4.1 虚拟头节点真的是“保命符”吗很多链表的删除、反转、合并操作都需要“可能更改头节点”的处理。虚拟头是一个指向原head的额外节点它可以让你对“第一个真实节点”的操作和对其他节点的操作完全一致不用写特殊分支。但是也别滥用。某些情况下虚拟头会造成误解特别是在“循环链表的区间反转”里处理不好会让dummy-next指错对象。我给自己的规定是只要设计到“头节点可能变”就无脑加虚拟头如果头节点绝对不会变就别画蛇添足。判断标准很简单——自己写两个测试用例一个是普通链表一个是空链表如果空链表让你写了特殊if那大概率就需要虚拟头来简化。4.2 循环终止条件的经典陷阱链表题里最常见的死循环源是把while (cur)写成while (cur-next)或反过来。这背后有两种遍历需求需要“访问当前节点的值”时用while (cur ! NULL)。需要“连接当前节点和下一个节点”时用while (cur ! NULL cur-next ! NULL)。比如找中间节点很多人用while (fast fast-next)。如果链表有偶数个节点循环结束时慢指针的位置是第二个中间节点如果有奇数个则是正中间。面试时一定要主动说明自己对这个细节有意识因为“链表长度为奇数/偶数”正是面试官最常出的变形考点。4.3 递归解法别忽略栈溢出风险链表是线性结构递归反转链表在链表长度超过一定量级时会爆栈。虽然面试时这个问题不一定能真正测出来测试链表不会特别长但技术总监轮就特别喜欢问这个问题你这个递归解法在长度100万时能跑吗这时候你要能接住可以把递归改写成迭代空间复杂度就从O(n)降到O(1)或者使用尾递归优化如果编译器支持的话。这个追问的本质是想考察你是否清楚抽象实现的代价而不是单纯背答案。我建议在面试中主动点出“递归版空间复杂度O(n)迭代版O(1)所以工程上我更倾向迭代”这句话说完面试官基本就跳过这一问了。4.4 测试用例设计边界条件全覆盖的第一道防线链表题的基本测试用例我自己固定为五条空链表head NULL单节点链表head只有一个节点两个节点涉及头节点变动的逻辑最容易在这里出错普通长度链表比如7个节点包含重复值的链表检验重复删除类逻辑不要小看这五条。很多人代码写对了但面试官让他“先自己测一下”的时候他只会跑一个标准用例结果边界问题全都留在面试官追问时才暴露。能主动说出“空链表、单节点、双节点”三个用例的人已经赢过一半候选人。4.5 调试技巧用printList函数快速看链表结构链表调试和数组不一样数组可以直接看某个下标的元素链表一旦指针指错你很难通过“输出某个节点”定位问题。我的做法是写一个printList工具函数能打印从头到尾的所有节点值。每次在一个操作之后立刻调用它观察链表的当前形态确认是否符合预期。void printList(struct ListNode* head) { struct ListNode* cur head; while (cur) { printf(%d - , cur-val); cur cur-next; } printf(NULL\n); }配合在关键操作前后加打印比如反转链表里在“断开”和“重连”之间打印一下很快就能定位是哪一步导致断链。这比在断点里一步步看指针值高效得多。我整理源码时几乎每个核心函数都留着这个调试函数的调用痕迹也算是给后来者的一份指引。5. 面试现场从“刷题”到“表演”的转变刷题和面试是两码事。题刷得好的人不一定面得好很关键的原因是面试不止考“你会不会写代码”还考“你怎么思考问题”以及“你如何与人协作”。链表题的代码量通常不长所以更考验你在白板前或者编辑器前的表达节奏。5.1 先开口说思路再动手写代码链表题拿到手不要一上来就写。先用一两分钟说清楚你打算怎么做哪怕只是说“我先判断空链表然后准备三个指针pre、cur、next进行反转”。这是给面试官的一个信号你不是在背答案而是有清晰的解题路径。技术总监轮我遇到过更刁钻的情况——他直接在我思考的时候打断让我“说出你现在脑子里想到的三种解法以及它们的空间复杂度”。经历过几次之后我养成了一个习惯看到任何链表题先在脑子里过三件事——能不能用双指针、能不能用递归、能不能用哈希表优化空间。无论最终选哪种至少要在开头主动提到其他可能性这会展示出你的知识广度。5.2 复杂度分析要主动、要准确链表题的空间复杂度有非常明确的规律只使用指针变量O(1)使用递归O(递归深度)使用哈希表/堆O(n)或O(k)时间复杂度的主要场景是单次遍历O(n)多次遍历O(n)K路合并O(n log k)。写完后不要等面试官问自己主动说“这个算法时间复杂度O(n)空间复杂度O(1)”会显得非常职业。有个小细节反转链表的迭代法空间是O(1)但如果你用递归空间就是O(n)。很多人在递归版里脱口而出“空间复杂度O(1)”这是会扣印象分的。所以每次设计到递归解法我建议主动补一句“如果我把递归改成迭代空间可以降到O(1)”这句话能一石二鸟。5.3 边界条件要主动提出不要等面试官逼问举例反转区间链表题我写完后会主动说“m1的情况我已经用虚拟节点处理了所以返回的dummy.next一定正确”。环形链表题我会说“如果head是空或只有一个节点直接返回false”。这种主动暴露边界场景的行为是面试中性价比最高的加分项。要建立起属于你自己的“边界问题清单”。链表相关的清单很简单空链表、单节点、双节点、头节点被修改、链表有环、链表长度是奇数/偶数、节点值全部相同。面试前对着这份清单挨个在脑子里跑一遍自己写过的题基本就不怕被追问了。5.4 手撕代码时的节奏与沟通面试手写链表代码建议你每一步都先写注释骨架再填充逻辑。比如先写// 保存当前节点的next // 将当前节点的next指向前驱 // 移动pre和cur再往里面填变量名和指针操作。这样做的好处是万一中途忘了某个变量名面试官看着注释也知道你想干什么他反而会觉得你的代码组织能力很强。如果发现自己写错了不用慌。直接口头说“我这里的边界有问题我改一下”然后迅速修正。面试官更看重你发现问题和自我修正的速度而不是一次成稿的能力。我自己在做K个一组翻转时第一轮也经常忘记在组内循环结束之后把pre更新到这一组的最后一个节点发现后更正面试官通常都会理解。6. 常见错误速查表与避坑心得以下内容来自于这份2万行源码的调试日志摘录每一条都是真实踩过的坑不是网上抄来的总结。读者可以直接收藏这份速查表刷题前扫一遍能帮你少烧几十个小时的脑细胞。典型错误具体表现根因分析正确做法断链反转链表时后半段丢失修改cur-next前没保存后继先用临时节点保存next再重连死循环链表遍历不结束循环条件写成cur-next但cur永远不为空分清楚用cur还是cur-next并用测试用例验证头节点丢失删除头节点后返回错误结果没有用虚拟头或单独处理设置dummy-nexthead操作完返回dummy-next递归爆栈长链表反转时程序崩溃递归深度过大改用三指针迭代法差一错误K个一组翻转漏翻或翻错循环次数n-m或k-1搞混用单节点、双节点用例验证快慢指针空引用环形链表判断时fast-next为空快指针先于慢指针走到尾部每次移动前检查fast和fast-next再分享几个个人体会很深的避坑技巧第一链表的“纸上跑一遍”价值远高于直接编码。遇到反转或者区间类题目花三分钟在纸上画出各步的指针指向再上编辑器写代码调试时间能缩短一半以上。我自己就把所有高频链表题的指针走向画成本子面试前翻阅一遍相当于把解题框架重新过了一遍。第二代码的变量命名直接影响你的思考清晰度。很多刷题者喜欢用p、q、r这种极简命名看起来简洁但调试时脑子要转好几道弯。我推荐用pre、cur、next、dummy、tail这种语义明确的命名虽然代码长一点但是在面试高压环境下语义清晰比代码长短重要得多。第三集中刷题比分散刷题有效。链表题建议抽一个晚上一口气刷十道以上因为题型之间有很强的关联性。先刷反转基础题立刻刷区间反转紧接着刷K个一组翻转你会感觉到解法之间的递进逻辑。如果今天刷一道、明天刷一道知识是割裂的很难形成框架。第四源码注释要写“为什么”不要写“是什么”。很多人的注释是// 将cur-next指向pre这等于把代码读了一遍毫无价值。真正有用的注释是// 这里先保存next否则修改cur-next后链表会断掉。在2万行源码的整理过程中我最大的一条感悟就是注释是写给三个月后的自己看的要能让你快速想起当时的思路而不是重复代码本身。回到面试本身链表题刷到这个程度剩下的就是心态了。我个人在实际操作中的体会是链表题是所有算法题型里“性价比”最高的一个刷题投入产出比极其可观——花一个周末集中突破这四类题型面试中遇到链表题时基本能形成条件反射写出正确代码的概率大幅提升。这也是为什么我反复强调要在框架层面吃透而不仅仅是一道一道背。最后再多说一句关于这份101榜单的误区。榜单的价值不在于题目本身而在于它把市面上高频出现的题型做了一个聚类。链表这部分只要能独立写出榜单中每一道题并清楚解释每一处边界处理的理由你的链表水平已经超过绝大多数候选人。如果还有余力建议进一步研究链表在LRU缓存、跳表设计中的应用那是链表从算法题走向工程实战的桥梁。你在刷题中积累起来的指针感觉和防御式编程习惯会在后续的系统设计中持续给你回报。