如果你刷LeetCode已经过了数组和字符串的阶段大概率会在链表这里卡上一阵子。链表题的单次通过率往往不高不是因为算法多难而是指针操作太容易出现看起来对、跑起来错的情况。这篇刷题记录是系列第5篇我专门把链表从热门100题里挑出来做了一次完整复盘整理了遍历、反转、双指针、合并相交这几类高频考法也把调试链表的经验单独写了出来。适合正在准备算法面试、或者刷题进度卡在中等难度链表题的同学参考。1. 链表在算法面试里的真实分量为什么值得为它单独开一篇刷题记录很多人刷LeetCode的习惯是跟着题号从头往后刷刷到链表题就顺手做掉觉得和数组题没什么区别。我早期也是这样直到一次模拟面试里手写反转链表翻车才意识到链表需要单独建立一套刷题方法论。先看数据LeetCode热门100题里链表相关题目大约有十五到二十道占比不低。而且链表题很少孤立出现它经常是后续复杂题的基础构件比如树的遍历本质上就是带两个next指针的链表节点的递归操作图的邻接表也大量复用链表思想。面试官爱考链表因为一道中等难度的链表题能在十五分钟之内考察三样东西数据结构基础是否扎实、代码控制力是否细腻、边界条件有没有形成肌肉记忆。这三个维度恰恰是工程岗日常写代码最需要的能力。链表题还有一个特点和其他数据结构题不一样数组题你写错了打印出来基本能定位问题链表题有时候打印都会死循环。它考的不是想不想得出来算法而是手上功夫稳不稳。这道题不管用什么语言核心难点都在指针或引用的重新指向顺序一步错就可能导致环或者丢节点而且肉眼很难发现。所以我把链表单独列成一个专题来刷。刷完一轮之后回头看收获最大的不是记住了多少道题而是总结出了套路反转类、快慢指针类、合并类、相交/删除类热门题基本都能归到这四类里。有了套路之后面对新题的第一反应不再是慌而是先判断它属于哪个框架再在框架里填细节。2. 动手前先补三个基础课节点定义、遍历终止条件、指针操作顺序2.1 C结构体定义与不带头结点到底意味着什么LeetCode上的链表默认是单链表节点定义用C写出来是这样struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} };刷题时需要意识到LeetCode的链表是不带头结点的单链表也就是说第一个节点就是有效数据节点没有额外的哨兵头节点。这个设定给很多操作带来麻烦如果要删除的是头节点那head head-next和prev-next cur-next是两种完全不同的写法必须分开处理。工程里常见的带头节点写法反而没有这个烦恼因为头节点永远不动逻辑统一。不带头结点还有一个衍生问题很多题要求返回新的头节点比如反转链表、删除节点、合并链表返回值有时候是原来的头有时候变成了原来的尾。如果你没有用虚拟头节点或者没有妥善保存新头函数一返回整个链表就丢了。2.2 遍历的终止条件while(cur)和while(cur-next)是两码事链表遍历看似简单终止条件却非常容易搞错。while (cur ! nullptr)表示要访问当前节点循环体内会用到cur-val或cur-nextwhile (cur-next ! nullptr)表示要访问的是下一个节点循环体内通常会修改cur-next的指向。这个区别在删除倒数第N个节点、找中间节点、判断回文链表时特别关键。我的经验是写代码之前先问自己一句循环结束时cur停在哪里如果希望cur停在最后一个有效节点上用while(cur-next)如果希望cur遍历到空为止用while(cur)。这两句话在代码里往往只差一个-next运行结果却天差地别。还有一个新手容易忽略的点遍历链表如果要往回找前驱单链表本身做不到必须额外用一个prev指针跟着cur走。我在刚开始刷题时总觉得麻烦后来看多了才发现链表题一半以上都在处理prev、cur、next三个指针的协同移动。2.3 插入删除的指针顺序为什么顺序错了节点就丢了给单链表插入一个节点标准写法是newNode-next cur-next; cur-next newNode;第一步必须先让新节点指向后继第二步再让当前节点指向新节点。如果两步顺序颠倒先把cur-next指向新节点那么原后继节点就彻底找不到了这就是经典的指针丢失。这个逻辑可以类比火车车厢的摘挂操作你想在2号车厢和3号车厢之间插入一节新车厢必须先把新车厢和3号车厢连好再解开2号和3号的连接。如果先把2号和3号解开3号车厢就溜走了。链表的插入删除以后端开发用得特别频繁这个比喻在面试里讲述代码逻辑时也很加分。删除节点的写法是prev-next cur-next; delete cur;这里的关键是必须有prev指针否则被删节点的前驱无法更新。所以在遍历时我习惯把prev初始化成nullptr每次循环结束前把prev更新为cur让前驱的位置一直跟得上。3. 链表题的核心就四个套路热门100题大部分跳不出这个框架3.1 反转类逆置链表的三种写法反转链表是链表题里的hello worldLeetCode第206题热门100题常客。迭代写法用三个指针ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* cur head; while (cur) { ListNode* next cur-next; cur-next prev; prev cur; cur next; } return prev; }很多人记代码能写出来但问他为什么能反转就说不清。核心在于每次循环只做一件事——把当前节点的next指向前一个节点。但是单向链表没有前驱信息所以需要prev记录前一个又因为一旦修改了cur-next原来的后继就丢了所以必须先用next存下后继。三步的顺序和上面说的插入操作一脉相承。反转链表还有递归写法代码更短ListNode* reverseList(ListNode* head) { if (!head || !head-next) return head; ListNode* newHead reverseList(head-next); head-next-next head; head-next nullptr; return newHead; }递归写法的理解关键在于递归函数返回的是反转后的新头head-next在递归返回时已经变成了反转后子链表的尾节点所以head-next-next head就是把当前节点接到尾节点后面。递归解法面试时会加分前提是你能把每一层的指针变化说清楚否则不建议硬背。Python的写法和C几乎一样只是不需要处理deletedef reverseList(self, head: Optional[ListNode]) - Optional[ListNode]: prev, cur None, head while cur: nxt cur.next cur.next prev prev cur cur nxt return prev这题练熟之后反转链表的前N个节点反转区间链表这些变体就都能做了。我的建议是把迭代版练到闭着眼睛能写递归版至少能手推一遍递归栈。3.2 快慢指针类环形链表和找中间节点是同一套思路快慢指针也叫双指针是链表题里应用面最广的技巧。LeetCode第141题判断链表是否有环标准解法就是快指针每次走两步慢指针每次走一步bool hasCycle(ListNode *head) { ListNode *slow head, *fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) return true; } return false; }为什么快指针每次走两步而不是三步四步因为步长差为1时快指针一定能追上慢指针如果步长差大于1慢指针可能被跳过去在某些环结构下永远追不上。这个细节面试官很喜欢追问。同一个思想还能解决两个常见问题找到链表中间节点快指针到头时慢指针正好在中点、找到环形链表的入环点需要多一步数学推导记住结论相遇后让一个指针从头出发另一个从相遇点出发每次都走一步相遇点就是入环点。找中间节点的代码把上面第141题循环体里的if判断去掉循环结束后slow就是中间节点。这个操作是回文链表题的预处理步骤也是重排链表题的前半段。所以别看快慢指针只是一个小技巧它串起来的题至少有三四道。3.3 合并类合并两个有序链表递归比迭代更容易理解LeetCode第21题合并两个有序链表是归并排序在链表数据结构上的最简版本。迭代写法推荐用虚拟头节点ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* tail dummy; while (l1 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 ? l1 : l2; return dummy.next; }这里的虚拟头节点dummy就是一个哨兵它让我们不用特判结果链表为空的情况代码统一且安全。函数末尾返回dummy.next完美规避了头节点不确定的问题。递归写法更简洁每次只比较两个头节点把小的摘下来然后递归合并剩下的链表。很多人觉得递归难懂我提供一个理解角度mergeTwoLists(l1, l2)的结果是一个有序链表这个链表的头节点就是l1和l2当中较小的那个。想通了这一点递归代码就只是把这句话翻译一遍。合并有序链表是排序链表题的核心子过程后者在LeetCode第148题属于链表的归并排序应用。如果能独立写出合并两个有序链表再把找中间节点、递归分解、合并这三个步骤拼起来第148题也就拿下了。3.4 相交与删除类长度对齐法和dummy节点的组合拳LeetCode第160题相交链表核心思想是让两个链表对齐。做法很直观先分别算出两个链表的长度长的那个先走长度差步然后两个指针同步走第一次相遇的节点就是交点。这里有一个不用算长度的技巧两个指针分别从A、B头节点出发走到尾部后跳到另一个链表的头节点继续走。如果两个链表有交点它们在第二趟会同时到达交点如果没有交点它们会在同一时刻到达null。这个写法的数学原理是两个指针走过的总路程都是lenA lenB所以最后必然对齐。代码比算长度更短但面试时最好把原理讲清楚不要假装是玄学。LeetCode第19题删除倒数第N个节点是虚拟头节点和快慢指针的经典组合ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode dummy(0); dummy.next head; ListNode *fast dummy, *slow dummy; while (n--) fast fast-next; while (fast-next) { fast fast-next; slow slow-next; } slow-next slow-next-next; return dummy.next; }快指针先走N步然后快慢指针同步走当快指针到达末尾时慢指针正好停在要删除节点的前驱位置。注意这里快指针先走N步还是N1步的差别先走N步然后判断fast-next可以让slow最终停在目标节点的前驱删除时不需要再往前找一步。写代码时这个边界特别容易多走或少走一步我的习惯是在草稿纸上用一个长度为5的链表、删除倒数第2个节点来推演一遍。4. 链表题调试的正确姿势纸上模拟、边界清单和虚拟头节点4.1 调试链表题为什么不能完全依赖打印数组题出错了打印整个数组一目了然。链表题也想当然地打印链表却可能遇到两个问题第一链表有环时打印永不终止程序直接卡死第二指针指向了错误但还未崩溃的节点打印出来的序列只显示当前状态根本看不出哪一步操作导致了错误状态。我的做法是代码写完先不跑直接在纸上模拟。拿一个短链表比如1-2-3-4把每一步当前指针指向谁、next被改成了谁写下来。链表题的循环通常只有两三步模拟一遍就能发现80%的问题。比如反转链表拿4个节点的链表走一遍迭代过程走到第三步时你就会发现如果忘记保存next后半段链表已经丢了。4.2 边界条件清单每个链表题提交前都要过一遍的检查项链表题翻车十有八九翻在边界条件上。我给自己定了一个检查清单每道题提交前口头过一遍空链表head为nullptr时代码会不会访问空指针单节点链表只有一个节点时反转、删除、找中点是否都正确两个节点的链表非常容易暴露快慢指针步数和prev更新问题头节点被修改的场景删除头节点、反转链表后返回值是不是新的头尾节点处理删除尾节点的循环条件是否会导致多走一步、访问空指针这个清单不是背出来的是踩坑踩出来的。我印象最深的一次删除倒数第N个节点没加虚拟头节点单独处理头节点删除时又忘了更新返回值连续报错三次才定位到问题。加dummy之后删除逻辑对头节点和中间节点完全一致这类问题几乎绝迹。4.3 虚拟头节点距离一次AC最近的技巧虚拟头节点dummy node是链表题里性价比最高的技巧没有之一。它的作用有两层一是消除头节点需要特判的代码分支二是保证头节点被修改后依然有办法拿到链表的真实开头。凡是可能修改头节点的操作我的默认选择都是先建一个dummyListNode dummy(0); dummy.next head;然后在操作过程中只动tail、prev、cur这类指针最后统一返回dummy.next。这样写的好处是代码里几乎不会出现head head-next这种需要额外判断的语句逻辑分支变少边界条件自然变少。合并有序链表、删除倒数第N个、两两交换节点、旋转链表这些题用dummy都能大幅降低出错的概率。4.4 链表题常见错误速查表错误类型典型场景解决方法指针丢失插入/反转时未先保存后继节点先用临时变量next保存cur-next死循环打印有环链表反转时忘了把最后一个节点next置空使用快慢指针判环反转结束后head-next nullptr空指针访问删除节点时cur为nullptr还取cur-val循环条件用while(cur)或while(fast fast-next)头节点丢失删除头节点或反转链表后返回了错误的头用虚拟头节点dummy统一处理遍历多走一步删除倒数第N个时fast走了N步还是N1步的混淆纸上模拟5节点链表标出fast和slow最终位置这个表我会贴在刷题笔记的开头每次写链表题之前扫一眼。时间久了这些错误会从需要刻意检查变成自然规避。5. 热门100题里的链表题目盘点以及工程中链表的另一种写法5.1 值得反复刷的热门链表题清单以下是我从LeetCode热门100题和日常面试反馈里筛出来的链表题覆盖了上面说的四个套路难度由浅入深题号题目核心考点难度206反转链表三指针迭代、递归简单21合并两个有序链表虚拟头节点、递归简单141环形链表快慢指针简单876链表的中间节点快慢指针简单160相交链表长度对齐、双指针简单19删除倒数第N个节点虚拟头节点快慢指针中等142环形链表II快慢指针数学推导中等148排序链表归并排序链表切分中等234回文链表找中点反转后半段简单143重排链表找中点反转合并中等2两数相加链表遍历进位处理中等我的刷题顺序建议是先把前六道简单题刷到不看题解能一次性写对再挑战142和148这种组合题。千万别一上来就做排序链表否则会同时被怎么找中点和怎么合并两个问题夹击容易劝退。5.2 周赛和组合题里链表常常换着法子出现最近几场周赛和热题里链表很少单独考一个知识点更多是和其他内容组合。比如LeetCode第2题两数相加本质是链表遍历数学进位考察的是你会不会在遍历的同时维护进位标志并且正确处理两个链表长度不一致的尾部情况。再比如反转链表II表面是反转实际还要先找到指定区间的前驱节点这就把找前驱和反转串到了一起。这类组合题的应对方法其实还是拆解看到一道新的链表题先问自己它由哪几个基础套路组合而成然后把每个部分分别搞定最后处理衔接处的边界。比如两数相加就是合并链表的遍历框架加法的进位逻辑重排链表就是找中点反转后半段交替合并。只要基础套路熟练组合题本质上只是时间问题。5.3 工程里的链表Linux内核的嵌入式双向循环链表刷题之余值得花十分钟了解一下工程中的链表写法它能帮你跳出LeetCode链表就是单链表的思维定式。以Linux内核里的list_head为例它的设计是不带头结点的双向循环链表节点结构把链表指针从业务数据里抽离出来通过内嵌list_head结构体把所有对象串起来。内核链表用的是这种侵入式设计遍历时通过container_of宏拿到外层结构体的地址。这和LeetCode的单链表长得完全不一样。我做了一个小对比对比项LeetCode链表内核list_head方向单向双向头节点不带头结点带头节点list_head作为哨兵指针位置业务数据内独立嵌入结构体插入手动维护节点list_add统一操作典型应用算法题管理进程、文件、缓冲区为什么要了解这个因为面试官如果问链表在工程里怎么用只会背LeetCode题解的人会答不上来。哪怕只是知道有这种设计也能体现你对数据结构的理解不是停留在刷题层面。5.4 Java和Python刷链表写法和C有什么差异Java里没有指针但引用和指针在链表操作上的语义完全一致你把一个节点的引用赋值给另一个变量操作这个变量就是在操作原节点。所以Java写链表题核心逻辑和C几乎一样只是不需要手动管理内存也不用写delete。Python的写法更简洁因为赋值即引用解包赋值还能一次完成多个变量的交换。Python实现链表反转时下面这个写法非常Pythonicdef reverseList(self, head): prev, cur None, head while cur: cur.next, prev, cur prev, cur, cur.next return prev注意这里用元组解包同时完成三个赋值不会出现中间变量覆盖的问题。但我不建议新手一开始就用这种写法还是先老老实实用临时变量保存next想清楚每一步的指针变化之后再追求代码的简洁。6. 我判断自己链表题刷合格的标准从会背答案到会设计解法刷了快两周链表题之后我给自己定了四条验收标准不是以AC数量为准而是以能不能应对没见过的新题为准。第一条给定一个链表场景能快速说出它属于哪类套路。看到反转想到三指针或递归看到环想到快慢指针看到删除合并想到虚拟头节点。这个反应速度靠大量刷题和复盘来形成没有捷径。第二条反转链表和合并有序链表这两道基础题能在五分钟内从零写出并且主动加上边界检查。这两道题是很多中等题的零件零件都不熟组装就会出问题。第三条能解释清楚每个技巧背后的原理而不是只会背代码。比如快慢指针为什么能判环、虚拟头节点为什么能统一删除逻辑、反转链表时next临时变量到底在保护什么。面试官最爱追问的就是这些。第四条写完代码后能主动列出边界条件并逐一验证。空链表、单节点、双节点、头节点修改、尾节点删除这五个检查点在潜意识里成为默认动作而不是提交报错之后才想起来。我的个人复盘方法也很简单每道链表题提交通过后把代码重新手写一遍到本地笔记然后在旁边注一行这题的坑在哪里以及用了什么套路。周末挑三道最不熟的题重新做不做对不结束。这个方法听起来笨但对我这种靠手感记忆的人来说特别有效。链表题刷到这个程度再去面对热门100题里那些所谓的中等偏难链表题你的心态会从这题好绕变成这不就是找中点加反转加合并吗。那个转变就是我从刷题走向会做题的分界点。