刷题这件事不少人一开始都栽在Day2链表上。代码随想录的链表章节我前后刷了三轮第一次是真没做出来第二次能做但一改就崩第三次才勉强达到面试能默写的程度。回过头看链表题写不出来卡住的从来不是语法而是脑子里对指针引用节点连接这些概念没有形成画面感。这篇文章就把我在Day2链表里趟过的坑、总结出来的套路和一些常规文档里不会写的经验一次性讲透。1. Day2的链表关卡为什么看懂了代码自己写还是崩先说个现象。很多人在数组那几天感觉还行一到Day2链表画风突变——看题解觉得这不就是改一下next嘛合上答案自己写不是空指针就是死循环调半天也不知道哪里断了。根子在于数组和链表的思维模型完全不同。数组是一块连续的内存arr[i] x这件事靠下标直接定位你不需要关心元素和元素之间怎么连接。链表不一样链表里的每个节点都是一个独立对象节点之间靠地址/引用衔接。A节点想找到B节点只能通过A的next指针没有第二条路。这个特性决定了链表题的每一步操作都必须回答一个问题当前这个节点是谁在指着它举个例子。删除一个中间节点在数组里是后面所有元素往前挪一格链表里则是让前一个节点的next跳过当前节点直接指向后一个节点。数组操作的是值链表操作的是连接关系。很多新手卡住就是因为脑子里还在用数组的搬值逻辑去理解链表自然处处别扭。另外不同语言在链表上的表达方式也不一样这又是一层障碍。代码随想录主推CListNode* cur head这种写法指针语义非常直接cur存的是一个地址cur-next是先沿着cur找到节点再取它的next字段。而在Python里万物皆对象cur head是让cur这个变量去引用同一个对象cur.next new_node是修改这个对象的属性理解上更接近Java引用但初学的时候容易把变量和对象混在一起一绕就晕。所以我的建议是用你主力刷题的语言把链表节点类的定义自己手写一遍写清楚它的属性和方法。这一步做完了后面所有题都会顺很多。以Python为例节点的定义通常长这样class ListNode: def __init__(self, val0, nextNone): self.val val self.next nextC版本则是struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} };别看这是个边角料步骤它决定了你对节点这个最小单位的认知。节点到底是什么、字段有哪些、怎么创建自己动手敲一遍比看十遍都有用。2. 动手写代码前先想清楚两件小事2.1 虚拟头节点让所有边界变成同一种情况链表题一个很经典的分叉点就是头节点的特殊性。假如你要删除一个值为特定数值的节点如果这个节点恰好是头节点处理逻辑和删除中间节点完全不同删除头节点得把头指针往后移一格删除中间节点得让前驱节点的next指向后继。这两种情况各写一份代码逻辑重复不说还特别容易在边界上漏掉某个分支。虚拟头节点dummy head解决的正是这个问题给它放在真正头节点的前面dummy.next指向链表的第一个有效节点。有了它之后链表里的每一个节点包括原来的头节点都有前驱了删除、插入的逻辑变得完全统一不再区分头和非头。操作的时候只要记住最后返回的是dummy.next不是head。dummy ListNode(nexthead) cur dummy # 后续所有操作都从cur出发 return dummy.next很多刷题教程会告诉你加个虚拟头节点就完事了但没讲清楚虚拟头为什么有效。它本质上是把头节点没有前驱这个特殊条件消掉了。链表题里凡是涉及删除、插入、交换、合并的加个虚拟头基本都能让代码从一堆if else变成一套通用逻辑。2.2 修改指针的顺序错了就整段断链链表操作里最容易被坑的是指针修改的顺序问题。往链表中间插入一个新节点看起来就两步新节点的next指向当前节点的后继当前节点的next指向新节点。但这两步一旦顺序反了链表会从中间断掉。假设你要在节点a后插入新节点nodea的next原本指向b如果先执行a.next node那么a指向了node但node还没来得及指向b——链表在a这里断了b再也找不回来。正确顺序是先让node.next a.nextnode先指向b再让a.next nodea指向node。这个顺序问题在链表题里反复出现。不光插入反转链表、交换相邻节点、合并两个链表全都要遵守先把新连接接上再断开旧连接的原则。直观的理解就是你动手切断旧绳子之前必须先确保新绳子已经挂好否则东西就掉了。我是把先接后断这四个字写在笔记最上面的后面做所有链表题都受用。2.3 画图这件事真的别省链表题不看图硬写代码基本就是和自己过不去。我见过太多人对着代码干想这里指向哪里那里原来是谁想十分钟想不明白其实画三秒钟的图就清楚了。具体做法很简单在纸上画出节点方块每个方块里写上val用箭头表示next。操作之前先画现状图操作之后画结果图然后把两幅图之间的差异转换成代码。多练几道题之后你会发现自己在脑子里也能虚拟画图了这时做题速度会明显变快。链表是少数画图比查文档更有用的知识点谁画谁知道。3. 移除链表元素把头节点边界从头到尾理顺这道题的描述比较清晰给你一个链表的头节点head和一个整数val请你删除链表中所有满足Node.val val的节点返回新的头节点。我最初写这道题完全就是按头节点特殊处理的思路来的代码写得又长又容易错# 方式一不带头节点的写法需要单独处理头节点 while head and head.val val: head head.next cur head while cur and cur.next: if cur.next.val val: cur.next cur.next.next else: cur cur.next return head两种逻辑分两条线走。先通过循环把开头一连串等于val的节点清掉然后从当前位置出发检查cur.next要不要删。注意中间还有个细节删了节点之后cur不动因为cur.next已经变成了新节点可能还等于val要继续检查只有不需要删的时候cur才前进一步。但这样写面试官多半会接着问一句如果不单独处理头节点能不能写得更简洁这时就该虚拟头节点登场了# 方式二使用虚拟头节点逻辑统一 dummy ListNode(nexthead) cur dummy while cur.next: if cur.next.val val: cur.next cur.next.next else: cur cur.next return dummy.next区别很明显有了虚拟头遍历的起点是dummy删除头节点和删除中间节点的逻辑变成完全一致——都是看cur.next的值决定要不要让cur.next跳过它。代码短了一半也不容易漏边界。补充一点关于C的细节如果你用C写这道题被删除的节点需要手动delete释放否则会内存泄漏。刷题平台一般不Care这个但面试时会有人问。工程上删除节点之后还要考虑是否把被删节点的next置空彻底断开引用避免悬空指针。这些属于语言层面的清理习惯刷题时可以顺手养成。这道题的时间复杂度是O(n)空间复杂度O(1)本质是单指针线性扫描。注意观察的话你会发现这里的cur指针从头到尾都是待删除节点的前驱这也是所有删除类题目的共同点——删除操作永远需要前驱节点来改连接。4. 设计链表用一道小题把增删改查全部串起来如果说移除元素是单点操作那设计链表这道题就是全家桶。题目要求实现一个链表类支持以下操作get(index)获取链表中第index个节点的值addAtHead(val)在链表第一个元素之前插入一个节点addAtTail(val)在链表的最后一个元素之后追加一个节点addAtIndex(index, val)在链表的第index个节点之前插入一个节点deleteAtIndex(index)删除链表中的第index个节点它把所有链表基本操作都塞进了一道题里。我推荐的做法是维护一个虚拟头节点dummy和一个变量size记录链表长度双管齐下后面的边界判断会轻松很多。核心思路是统一找前驱。第index个节点的前驱就是dummy往后走index步到达的节点。这一点适用于get、addAtIndex、deleteAtIndex三件事。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next class MyLinkedList: def __init__(self): self.dummy ListNode() self.size 0 def get(self, index: int) - int: if index 0 or index self.size: return -1 cur self.dummy.next for _ in range(index): cur cur.next return cur.val def addAtHead(self, val: int) - None: node ListNode(val) node.next self.dummy.next self.dummy.next node self.size 1 def addAtTail(self, val: int) - None: cur self.dummy while cur.next: cur cur.next cur.next ListNode(val) self.size 1 def addAtIndex(self, index: int, val: int) - None: if index self.size: return if index 0: index 0 pre self.dummy for _ in range(index): pre pre.next node ListNode(val) node.next pre.next pre.next node self.size 1 return def deleteAtIndex(self, index: int) - None: if index 0 or index self.size: return pre self.dummy for _ in range(index): pre pre.next pre.next pre.next.next self.size - 1几个值得注意的细节第一个是addAtIndex里index size要放行。index等于size意味着插到链表末尾也就是addAtTail的效果这是合法操作。只有index大于size才直接返回。很多版本在这里容易把等号写丢一丢尾部插入就废了。第二个是addAtIndex里index小于0的处理。题目描述里说index为0或者负值都插到头部所以代码里统一把负数改成0再走同一套逻辑。第三个是删除/插入节点之后size必须同步更新。这不是难事但特别容易被忘记。size一旦和真实链表长度不一致get和deleteAtIndex的边界判断就全是乱的而且这种Bug藏得深不画调试数据根本发现不了。第四个是遍历次数。可以这样记找第index个节点从头走index步找第index个节点的前驱也从dummy走index步两者步数相同。代码里get走的是dummy.next出发的index步addAtIndex/deleteAtIndex走的是从dummy出发的index步含义不同但步数一致写的时候注意起点别混。这道题在LeetCode上对应第707题属于中等难度但它的步数逻辑吃透了后面很多中等偏上难度的链表题都会轻松很多。5. 反转链表双指针和递归两条路都要能走反转链表是Day2里最经典、也是被面试官翻牌子最多的题目。题面很简洁给你单链表的头节点head反转链表返回反转后的新头节点。输入1-2-3-4-5输出5-4-3-2-1。5.1 双指针法理解逐个倒向迭代反转的核心思想是逐个改变每个节点的next方向。三根指针一起走prev指向当前节点的前驱cur指向当前节点temp用来暂存cur的下一个节点。循环里做四件事用temp存cur.next让cur.next指向prev然后prev挪到curcur挪到temp。当cur走完整条链指向空时prev恰好停在新链表的头节点上。class Solution: def reverseList(self, head: ListNode) - ListNode: prev None cur head while cur: temp cur.next cur.next prev prev cur cur temp return prev新手最常见的错误就是忘了temp cur.next。直接写cur.next prev那cur原来指向的下一个节点就再也找不回来了链表当场断成两截。这也是先接后断原则的再一次体现在断开cur和下一个节点之间已有连接之前必须先把它暂存起来否则后续遍历无处可走。对于这题为什么最后返回prev可以这样看cur走到None退出循环时prev指向的是最后一个非空节点这个节点因为一路反转变成了整条链的最前端所以它就是新链表的头。5.2 递归反转从后面已经反转好了开始想递归写法的思路和迭代完全不同。它把问题拆成这样假设从head.next开始往后的链表都已经反转好了现在只需要把head放到反转后链表的末尾事情就成了。话句话说head.next.next head让head的后继反过来指向head再head.next None断掉原方向的引用最后把递归返回的新头节点一路抛上去。class Solution: def reverseList(self, head: ListNode) - ListNode: if not head or not head.next: return head new_head self.reverseList(head.next) head.next.next head head.next None return new_head这个写法终止条件是not head or not head.next——链表为空或只有一个节点。这两种情况根本不需要反转原样返回就行。很多人的困惑集中在head.next.next head这一步。文字不好描述画图最直接把链表想象成1-2-3-4-5递归先进入(2-3-4-5)假设它返回的是5-4-3-22变成新链的末尾。回到最外层时head是1head.next是2。让head.next.next指向head相当于把2的next指向1于是整个链是5-4-3-2-1再把head.next置空斩断1到2的原连接一个完整的反向链表就出现了。两个版本的时间复杂度都是O(n)空间上前者O(1)后者O(n)——递归栈占空间。面试时如果没特殊要求我倾向先写迭代因为不依赖系统栈也不容易栈溢出。但递归也要会因为面试官很喜欢让你再写个递归版本看看而且后续二叉树的递归题和这个写法在结构上是一脉相承的。5.3 两种写法怎么选我的建议是练习阶段两种都写以明天能默写出来为标准。迭代版本帮助建立指针流动的感觉递归版本帮助建立递归函数返回什么的思维习惯。后者在Day2可能觉得绕但到了二叉树专题你会感谢这个节点。6. 刷完链表Day2我的几个亲测心得链路表的题真正做顺之后以下几个体会我觉得比单题解法更值得分享。第一个是先画图再走代码。现在我做链表题默认流程是先在纸上画出一个三节点的链表标好虚拟头的位置然后手动模拟一遍操作过程确认清楚谁是前驱、谁是next、哪个引用该被改再动键盘。画图不是浪费时间它是在给大脑建立正确的指针流动模型模型一旦建立代码几乎是看图直译。第二个是空指针检查做在前面。C/C、Java里访问null节点的next直接崩Python里抛AttributeError。链表题里大量bug都源于对链可能为空、节点可能不存在的预判不足。像get这种接口查询前必须先检查index合法性像addAtTail这种操作必须考虑原链表为空时也一样要能成功追加。边界越早处理后面主逻辑越干净。第三个是表达式cur.next出现的地方往往就意味着我要修改连接关系表达式cur.val出现的地方往往意味着我要读取数据。把这两种操作分开看代码会清晰很多不会混着改着就把链搞乱了。最后一个心得关于看答案和自己做出来的差距。链表这个专题是最能直观感受到看懂了但写不出来的专题也是最容易因为看懂而放松警惕的专题。我的经验是看完题解之后一定要合上答案自己从空编辑器开始重写一遍而且要在纸上模拟一遍。能独立写出来才算真的掌握。Day2链表的内容到这里核心的几道题我都用最笨的办法过了一遍。如果你正在被链表的边界条件折磨我建议你也像我一样每个操作都画图验证宁可慢一点也别跳步骤。链表这种东西一旦建立起正确的画面后面做再复杂的题都不会虚。