链表这东西力扣上换着花样出题但骨子里考的就那几件事遍历、反转、双指针、删除。很多人在新手期被它绊住真不是智商问题是没把链表的“内存结构”在脑子里建模出来。我刷了大几十道链表题之后最大的感悟是——单向链表所有的操作本质上都是在玩指针的重连而玩明白指针重连的那几个固定招式剩下就是套模板的事。这篇不聊高深理论就按我实际的刷题路径把单向链表的高频考点、解题模板、还有那些特别容易踩的坑一次性说透。适合刚开始刷链表、或者刷了一些但总是卡壳的人。文章里的代码以C为主思路是通用的你用Java、Python、Go都完全能照着迁移。1. 先别急着写码把单向链表的结构在脑子里建个模很多人链表题做不出来第一步就输在没理解“节点”到底是个什么东西。数组是一排连续的内存格子你知道第一个格子在哪儿往后数偏移量就能找到任意一个元素链表不是链表是每个节点“随身携带”一个指针指向下一个节点的地址。这意味着你想访问第100个节点必须从第一个节点开始一个next一个next地走过去没有任何捷径。1.1 节点的定义和常见写法链表题的第一步永远是定义好节点结构。虽然在力扣上这些定义已经帮你写好了但自己面试或者做项目时还是要能随手写出来struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} };这里面的关键就是那个next指针。它存储的是下一个节点的地址而不是下一个节点的“值”。每次做cur cur-next这种操作翻译成人话就是“把cur指针移动到下一个节点”。1.2 理解指针移动与断链的底层逻辑刷题时最常犯的错就是操作链表时把“指针遍历”和“修改next指向”混为一谈。你比如写cur cur-next这只是在遍历链表本身的结构没有发生任何改动但如果你写cur-next pre这就是真的在改链表结构了它把当前节点的next指向了之前的节点立刻就会引发“断链”。刚开始我老搞混这两件事导致反转链表时指针乱飞程序直接崩。后来我找到一个特别好的类比——链表就像一条绳子上的绳结每个绳结里有一根线头指着下一个绳结。遍历就是在顺着线头看下一个绳结是谁修改next就相当于把某个绳结里的线头拔出来重新绑到另一个绳结上。拔出来重绑的瞬间原来的链路就断了。所以每次操作链表之前脑子里要先问自己一句我这里改的到底是“指针在走”还是“链表在变形”2. 单向链表刷题的核心兵器库链表题虽然多但归结起来核心的几件兵器必须练熟。它们就像格斗里的基础拳法每一招都出现在无数题目当中。2.1 虚拟头节点处理边界条件的定海神针链表题目中头节点常常是个烫手山芋。你要删除头节点怎么办要在头节点前面插入怎么办如果不用虚拟头节点就得单独对head nullptr或者删除的是head这种特殊情况写if判断非常容易漏。虚拟头节点的思路特别简单在真正的头节点前面加一个额外的节点它的next指向head。这样无论怎么操作整个链表都有一个“前置节点”兜底你不需要再针对原始头节点做特殊处理。ListNode* dummy new ListNode(0); dummy-next head; ListNode* cur dummy; // 各种操作 return dummy-next;我实测下来虚拟头节点至少能省掉一半的边界条件判断。尤其是做“删除倒数第N个节点”、“两两交换链表中的节点”、“合并K个升序链表”这类题没有dummy节点代码会写得很狼狈。2.2 快慢双指针找中点、判环、找倒数第N个的一招鲜双指针是链表题里最优雅的武器没有之一。核心思路是让两个指针以不同速度遍历链表。找链表中点快指针每次走两步慢指针每次走一步。快指针到终点时慢指针正好在中点或者中间偏右取决于题目要求。判断环形链表也是快慢指针如果有环快指针一定会“追上”慢指针两者相遇如果没环快指针会先走到nullptr。找倒数第N个节点快指针先走N步然后快慢一起走。快指针走到终点时慢指针正好在倒数第N个节点。快慢指针最让我觉得妙的地方是它不算任何“长度”不需要先遍历一遍数出链表长度而是用“速度差”来间接测量代码量少还不容易出错。2.3 反转链表递归与迭代两条路线反转整个单向链表是几乎所有链表难题的“前置技能”。比如回文链表要先找中点再反转后半段K个一组反转链表就是把若干段反转连起来。迭代写法是最直观的需要三个指针pre前一个节点、cur当前节点、tmp下一个节点。每次循环做的事就是先保存当前的next再把当前的next指向前一个然后三个指针整体后移。ListNode* reverseList(ListNode* head) { ListNode* pre nullptr; ListNode* cur head; while (cur ! nullptr) { ListNode* tmp cur-next; cur-next pre; pre cur; cur tmp; } return pre; }这里最容易踩的坑是改cur-next之前必须先保存cur-next原本的值。因为一旦把cur-next指向pre原来的下一个节点就“找不着了”如果你没提前用tmp保存整个链表就断了。递归写法更短但理解起来稍微绕一点。它的思路是先反转head后面的整条链表再把head拼接到反转后的链表末尾ListNode* reverseList(ListNode* head) { if (head nullptr || head-next nullptr) return head; ListNode* newHead reverseList(head-next); head-next-next head; head-next nullptr; return newHead; }递归写法的关键就两行head-next-next head;是把后一个节点的next指回当前节点head-next nullptr;是断开当前节点原来的指向防止形成环。我建议两种写法都要会因为有些题比如K个一组反转用迭代思路更直观有些题比如从后往前处理用递归思路更省事。3. 高频题型的实操拆解从题意到代码的完整推导兵器练好了接下来就看实战。这一节我挑了五类最经典的链表题每一类都代表一种独立的解题范式。我会按“题目要求 - 思路推导 - 关键代码 - 坑点提示”的结构去拆尽量还原我当时做题时的完整思考路径。3.1 删除倒数第N个节点虚拟头节点双指针的经典组合这道题对应的力扣编号是19。要求给定一个链表删除链表的倒数第 n 个节点并返回链表的头节点。先说为什么不用“先算长度再正着删”的朴素做法。虽然那样也能做但要遍历两遍链表。用双指针可以做到一趟完成而且在面试场合下“一趟完成”本身就是加分项。思路推导创建虚拟头节点dummy让dummy-next head。定义fast和slow两个指针初始都指向dummy。fast先走n1步。为什么是n1因为当fast走到nullptr时slow要恰好停在待删除节点的前一个位置才能执行删除操作。fast和slow同步前进直到fast走到nullptr。此时slow-next就是要删除的节点执行slow-next slow-next-next。关键代码ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy new ListNode(0); dummy-next head; ListNode* fast dummy; ListNode* slow dummy; while (n-- 0) fast fast-next; while (fast-next ! nullptr) { fast fast-next; slow slow-next; } slow-next slow-next-next; return dummy-next; }这里面两个细节我要着重敲黑板fast先走的步数是n1还是n区别很大。如果fast先走n步那么当fast走到nullptr时slow恰好停在被删节点本身上没法做删除操作你没法删自己因为你只知道前一个节点才能修改next。所以要么先走n1步让fast停在nullptr前面的位置要么用fast-next ! nullptr作为循环条件让slow停在待删节点的前驱。返回值必须是dummy-next而不是head。因为如果要删除的正好是原头节点head已经变成“游离”的旧指针了返回它就出错。3.2 环形链表判断快慢指针的追逐问题对应力扣141题判断链表中是否有环。进阶版142题还要找到环的入口。这两道题是双指针的巅峰应用我第一次看141题时完全没头绪因为链表有环的话普通遍历会陷入死循环。思路核心用一个慢指针每次走一步一个快指针每次走两步。如果有环快指针终会在环内“追上”慢指针表现为fast slow时二者相遇。如果没环快指针会先一步走到nullptr。bool hasCycle(ListNode *head) { ListNode *slow head, *fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) return true; } return false; }这里要特别注意循环条件的写法fast ! nullptr fast-next ! nullptr。因为fast一次走两步如果fast已经到链表末尾了再访问fast-next就会对空指针解引用直接崩溃。142题找环入口就更有意思了它用到了一个非常经典的数学结论快慢指针相遇后把其中一个指针移回起点然后两个指针每次都走一步它们再次相遇的位置就是环的入口。我当时自己推导了半天核心逻辑是设链表起点到环入口的距离为a入口到相遇点的距离为b环长为c快指针走的距离是慢指针的两倍列方程就能解出从相遇点继续走a步正好到入口。这个结论可以当作模板直接用但面试时如果有余力最好能把推导过程说清楚。3.3 合并两个有序链表虚拟头节点在链拼接中的妙用对应力扣21题将两个升序链表合并成一个新的升序链表。这是链表题里的“入门必刷”也是后续“合并K个升序链表”的基础。思路特别直观两个链表从头开始比较谁的节点值小就把谁接上新链表的尾部然后对应的指针后移。关键在于新链表的头从哪里来如果用虚拟头节点整个拼接过程就可以统一处理不需要单独判断谁是头节点。ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode* dummy new ListNode(0); ListNode* cur dummy; while (list1 ! nullptr list2 ! nullptr) { if (list1-val list2-val) { cur-next list1; list1 list1-next; } else { cur-next list2; list2 list2-next; } cur cur-next; } cur-next (list1 ! nullptr) ? list1 : list2; return dummy-next; }这种做法的时间复杂度是O(mn)空间复杂度O(1)是标准最优解。还有一个递归版本大概只有四行但返回条件里的空值判断需要想清楚否则容易别扭。我的建议是合并两个有序链表用迭代版本理解最舒服递归版本作为思维训练可以看看别死记。3.4 反转链表II区间反转的边界处理力扣92题反转从位置 left 到 right 的链表节点。这题和“反转整个链表”最大的不同是你只反转中间一段前后的部分要保持原样。解题思路也不难核心还是虚拟头节点配合指针定位走到left节点的前一个位置记为pre。从left开始对长度为right-left1的这段子链表做反转。把反转后的子链表和前后部分接回去。实现时最稳妥的做法是“头插法”遍历子链表每遇到一个节点就把它插到pre的后面。这样不需要先反转再拼接直接在遍历中完成区间反转。ListNode* reverseBetween(ListNode* head, int left, int right) { ListNode* dummy new ListNode(0); dummy-next head; ListNode* pre dummy; for (int i 0; i left - 1; i) { pre pre-next; } ListNode* cur pre-next; for (int i 0; i right - left; i) { ListNode* tmp cur-next; cur-next tmp-next; tmp-next pre-next; pre-next tmp; } return dummy-next; }这段代码我第一次看的时候觉得像天书但动手画图就会明白每次循环都在把“当前节点的下一个节点”拽到pre后面相当于一个个往pre后面头插。头插法的好处是代码统一不需要考虑pre怎么接回去的问题因为pre-next始终指向最新插入的节点。3.5 两两交换链表中的节点画图是唯一解药力扣24题给定一个链表两两交换其中相邻的节点并返回交换后的链表。这道题如果不画图十个人有九个会指针绕晕。我公开一个自己用过的笨办法拿张纸画出四个节点标清楚每一步的指针指向变化。整个过程其实就是“拆开-重连”三个步骤dummy指向第二个节点交换后它变成新的“第一个”。第一个节点指向第三个节点。第二个节点指向第一个节点。移动操作指针到第三个节点前的位置继续下一对。写成代码是这样ListNode* swapPairs(ListNode* head) { ListNode* dummy new ListNode(0); dummy-next head; ListNode* pre dummy; while (pre-next ! nullptr pre-next-next ! nullptr) { ListNode* first pre-next; ListNode* second pre-next-next; first-next second-next; second-next first; pre-next second; pre first; } return dummy-next; }做这题最大的心得是不要试图在脑子里同时跟踪所有指针要相信一张图、一支笔的力量。先画出四个节点、标好当前pre的位置然后按顺序写出每一步的指针变化写完后对照图检查一遍。链表题里80%的混乱都是因为脑子里的指针状态和代码实际的操作已经对不上了。4. 刷题过程中的突出问题与排查经验链表题入门时会出现很多“看起来一样但结果不对”的情况很多坑我反复踩过。这节就整理几个最高频的报错场景和排查思路算是给自己也给大家留一份避坑手册。4.1 常见的空指针问题刷链表题最经典也最崩溃的报错就是“member access within null pointer of type ListNode”。意思是对一个空指针访问了它的成员。排查思路很固定检查你访问的每一个指针在访问前是否确保它不是nullptr。优先检查这五个位置while循环的条件里同时访问了cur和cur-next要注意短路问题。C里左侧为false右侧不会执行所以while (cur ! nullptr cur-next ! nullptr)是安全的但如果你写成while (cur-next ! nullptr cur ! nullptr)一旦cur为nullptr左侧就崩了。快指针走两步时必须确认fast ! nullptr fast-next ! nullptr少一个都不行。反转链表迭代写法中保存tmp之后再改next顺序不能反。虚拟头节点返回时确保dummy的next设置过否则返回的就是空节点。删除节点时确认删除的节点确实存在尤其是指针已经移动到nullptr附近时。这类问题的根源是很多初学者在写代码时没有形成“先判空再解引用”的肌肉记忆。链表这种结构天然就是一路next访问下去每跳一步都可能踩空所以写每一行涉及指针访问的代码前脑子里都要过一遍“这里会不会为空”。4.2 死循环问题环的形成与排查死循环的典型表现是程序卡住不动或者报“Time Limit Exceeded”。刷链表题时死循环几乎总是因为你无意中让某个节点的next指向了自己所在链路上的节点形成了环。最常见的两种误伤场景反转链表时忘记把原头节点的next置为nullptr。比如递归反转链表中如果少了head-next nullptr这一行结果链表末尾的节点会形成一个自环。链表的指针重连顺序写错导致某个节点在还没断开的情况下被两个前驱同时指向。排查死循环的方法是先在小链表上手动走一遍比如1-2-3把每步的指针打印出来。检查每个节点的next是否指向了链表的前面某个节点。重点检查反转过后的链表尾节点它应该是nullptr而不是指向之前的某个节点。我还犯过一个特别低级的错误在两个指针移动时忘记把其中一个后移导致快指针永远追不上慢指针循环退不出去。所以循环体内每写一次指针后移我都要检查“这次操作里所有应该移动的指针都移动了吗”。4.3 修改链表结构时的顺序禁忌链表题里指针重连的顺序极其讲究。你不是随便怎么写都能得到对的结果顺序错了轻则结果不对重则直接崩。我总结了一个核心原则在修改任何节点的next之前先确保它的下一个节点已经有人保存。以反转链表为例。你要执行cur-next pre但在执行之前必须先把cur-next原来的值保存在tmp里。因为赋值一旦发生原来的下一个节点就“失联”了。链表和数组最大的不同是数组元素移动后数据还在原地链表的节点一旦没有指针指向它你就再也找不到它了。同理在“两两交换”和“区间反转”这类涉及多个指针重连的题目里正确的操作顺序一定是“先保存再重连”。我把这个写成了一句话提醒自己保存后继再改指向最后移动指针。这九个字救了我很多次。5. 从“会做题”到“会解一类题”链表的框架思维题刷多了会逐渐发现链表的很多题目看起来完全不一样但解法骨架是同一个。如果你只是死记每道题的代码下次遇到变体照样抓瞎。这一节我想聊的是更高一层的整理方式——怎么把单道题抽象成模板形成自己的解题框架。5.1 链表题目的两大基本操作模式我复盘刷过的60多道链表题后发现绝大多数题目都逃不出两个操作模式模式一是“穿针引线式”核心是“找节点重连指针”。比如反转链表、删除节点、合并链表本质都是把某些节点的next重新指向合适的位置。这种题考察的是你对“前驱-当前-后继”三层指针关系的掌控力。模式二是“双指针扫描式”核心是“用不同速度或位置的指针遍历并找到目标位置”。比如找中点、判断有环、找倒数第N个节点本质都是双指针的位置配合。这种题考察的是你能否设计出合适的指针步进策略。拿到一道新题先问自己属于哪个模式再决定用哪套模板比我以前拿到题就闷头刷效率高太多了。5.2 链表题目的通用心法先画图再想边界不管题目怎么变我总结的做题流程始终是那几步第一步画图。把链表画成一个个方框用箭头表示next把题目要求的操作在图上走一遍。这一步做完60%的情况你已经知道该怎么写了。第二步想空值。把“链表为空”、“只有一个节点”、“只有两个节点”这种极端情况在图上走一下。链表题最大的失分点往往不是核心逻辑不对而是边界条件没处理干净。第三步套模板。判断是双指针扫描还是穿针引线选择对应的模板再结合题目特性做微调。这个流程不是天生的是我刷吐了N道题之后才总结出来的。现在我做一道新链表题落笔写代码之前必定先画图、想边界、定模板。哪怕题目很简单我也不会跳步。因为这个习惯救过我太多次了。5.3 刷题顺序建议从易到难的进阶路线最后给一个我个人认为比较顺畅的刷题路线按难度递进每类都对应力扣上比较有代表性的题目第一梯队手动熟悉141环形链表、21合并两个有序链表、206反转链表。这三道题是基础中的基础尤其反转链表建议迭代和递归两种方法都练熟。第二梯队虚拟头节点与双指针19删除倒数第N个节点、876链表的中间节点、83删除排序链表中的重复元素。这一梯队能帮你把dummy节点和双指针操作形成肌肉记忆。第三梯队综合应用92反转链表II、24两两交换链表中的节点、234回文链表。这些题开始综合运用多个技巧比如回文链表需要找中点反转后半段。第四梯队挑战25K个一组翻转链表、138复制带随机指针的链表、23合并K个升序链表。这些是面试里偏难的一档能稳定写出来就说明链表基本功非常扎实了。建议按这个顺序刷每道题做完之后不要急着刷下一道先问自己三个问题我用的思路是什么模板如果换一组数据会不会出问题这道题能不能用另一种方式做我实测过带着这三个问题复盘一道题效果远胜闷头刷五道。单向链表题其实就这么多套路。很多人觉得链表难是因为大脑更擅长处理“连续”的东西而链表是“离散”的天然需要我们额外建一层“跳转”的抽象。但只要把节点结构、指针重连、双指针这几件事彻底想明白再多的链表题也就是这些工具的不同组合。最后再分享一个小技巧遇到卡壳时别硬盯着代码空想把链表画在草稿纸上照着图一步步操作很多问题都能自己解开。刷题本质上是在训练手脑配合画图就是这种配合里最踏实的桥梁。