我先把结论放在前面链表这类题在LeetCode上属于典型的“看着简单、一写就错”。数组问题写错了多半是边界管得不好链表问题写错了几乎都是因为对指针变化时机的理解不到位。而“移除链表元素”和“反转链表”这两道题恰好把链表操作里最核心的两种基本功——删节点、改指向——一次性覆盖了。把这两道题吃透后面再做合并有序链表、两两交换节点、判断环形链表之类的问题会轻松很多。这篇文章适合正在刷题准备面试的朋友也适合刚学完数据结构、想把这些基础操作真正落到代码里的同学。我不会只贴一个能通过的答案而是把为什么这么写、哪里容易错、画图时应该盯住哪些地方都讲一遍争取看完之后你能闭着眼在白板上把这两道题写出来。1. 先说清楚链表操作到底难在哪很多人第一次接触链表都会觉得“这不就是结构体里加个指针嘛”结果一上手写删除、反转逻辑就开始打架。原因很简单链表这套东西语法层面确实不难难的是它和数组处理的思维方式完全不同。1.1 从一块数据积木说起节点与指针链表里的节点说白了就是一块存了数据、还带了一个“指向下一个节点地址”的变量。单链表里每个节点只有一条“线”通向后面所以它天生就是一条单行道。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next这段代码是LeetCode里最常见的链表节点定义。val 存值next 存下一个节点的引用。就这么点东西但所有的链表操作本质上都是在回答一个问题当前有几个指针分别指着谁接下来要让谁指向谁。数组里想做删除是把后面的元素整体往前搬。链表里想删除一个节点只需要让前一个节点的 next 跳过它、指到它的下一个节点就行。听起来更简单但问题是数组里搬元素的时候原数组还在原地你有的是时间慢慢改链表里一旦你把某个节点的 next 改了原来的指向就没了一旦没了记录你手头又没有别的指针指着它那就找不回来了。我见过太多人在这里翻车想删 cur 这个节点脑子一热直接写cur.next cur.next.next然后发现链表断了因为根本没有记录前一个节点是谁。你手里只有一个 cur 去遍历它往前一走前面那个节点就没人管了。1.2 链表操作的三条心法画图、保引用、三步走这三条是我自己反复撞墙之后总结出来的适用于所有链表题。第一条动手写代码前先画图。别嫌麻烦。你随便画四个方框代表节点用箭头连起来然后拿笔模拟指针移动。大部分链表题的思路画完图就自己浮出来了。很多人在脑子里空想越想越乱其实就是没把内存里的指向关系实体化。第二条改指针之前先保住要丢的引用。这一点是链表操作里最核心的工程素养。想象你要把一个节点从链上摘下来或者要反转两个节点的方向总有一个 next 会被覆盖。被覆盖之前你得先把那个值存下来存到临时变量里。这就是面试官常说的“备份 next”。做题的时候凡是发现某一步要改 next立刻问自己一句改了之后原来指向的那个节点还能不能找到找不到就加个临时变量。第三条任何一步操作都遵循“先断后接、保旧再换新”的顺序。可以先画三条线标清楚当前这几个指针的状态然后按顺序执行先用temp保存即将失去引用的节点再改A的next指向B再改B的next指向A……每一步之间不要跳。链表题之所以容易错就是因为代码很短、步骤很密集脑子稍微快进一下就把顺序弄反了。这三条心法放到所有链表题里都适用后面的两个题目我也会反复回到这些原则上。2. 移除链表元素真正难处理的其实是“头”题目本身不复杂给定一个链表的头节点 head 和一个整数 val删掉链表中所有值等于 val 的节点返回新的头节点。这是LeetCode第203题也是一道“送分题”但它的送分程度取决于你是否处理对了头节点。头节点一旦特殊化很多人就开始漏判。2.1 题目和第一反应单指针遍历会漏掉什么大多数人第一反应是遍历链表看到一个节点的值等于 val就把当前节点删掉。可问题是删除一个节点必须要知道它的前一个节点是谁。用单指针 cur 遍历的时候你发现当前节点要删你根本不知道它的前一个节点在哪于是只能另想办法。最容易想到的笨办法是单独处理头节点。先写个循环不停地看 head 的值是不是 val是的话 head 就往后挪处理完头节点之后再从新的头节点往后遍历用前一个节点 pre 来执行删除。这个方案能跑逻辑也对但代码写得比较别扭而且新手特别容易在处理完头节点之后忘了更新遍历起点。还有一种更极致的情况如果整个链表的值全是 val比如 head 是1-1-1-1要删掉所有 1。用上面的笨办法单独处理头的循环会一直把头往后挪直到 head 变成 None这时候函数返回的就是一个空链表。逻辑没问题但很多人写到这里会开始怀疑人生觉得空链表也要单独考虑。2.2 虚拟头节点让删除逻辑统一我强烈建议从一开始就用虚拟头节点dummy head的写法。它的思想很简单在真正的头节点前面再造一个节点它的 next 指向 head。这样整个链表的每一个节点都变成“有前驱”的节点了删除逻辑可以被统一处理不需要再为头节点单独开一条分支。def removeElements(head: ListNode, val: int) - ListNode: dummy ListNode(0) dummy.next head pre dummy cur head while cur: if cur.val val: pre.next cur.next else: pre cur cur cur.next return dummy.next这里最关键的是一点pre 什么时候动、什么时候不动。如果当前节点 cur 被删掉了pre 不能动。因为 pre 的下一个节点已经变成了 cur 的下一个节点这个“新的下一个节点”还没被检查过下一次循环里 cur 会指到它如果 cur 不需要删除pre 才移动。有人可能会问cur 都已经指向被删节点了cur cur.next还能拿到它原来的下一个节点吗当然能因为cur.next这个引用在你删除动作发生之前就已经存在了删除只是修改了 pre.nextcur 自己还握着自己原来的 next 指向呢。这就是链表的特性一个节点可以同时被多个变量指着你改掉其中一个变量的指向其他变量不受影响。你可以对比一下没删的时候和删了之后的状态状态precurpre.next删除前指向前一个有效节点指向待判断的节点cur删除操作后指向cur原来指向的下一个节点仍然指向被删节点本轮用完即弃cur.next下一轮循环可能不动或移动到cur的位置移到原cur.next取决于新节点是否删除这个表格我建议你配合代码一起看。逻辑清楚了代码就是几行的事。2.3 双指针版本pre 和 cur 的配合虚拟头节点版本的另一种常见写法是双指针其实上一个代码已经就是双指针了。pre 永远指向“最后一个确定不需要删除的节点”cur 负责往前探索。每当 cur 发现一个要删的节点pre 就直接把 cur 从链表中摘出去每当 cur 发现一个不用删的节点pre 就往前走一步和 cur 保持同步。这种写法的核心是pre 和 cur 之间既可能齐头并进也可能隔着被删掉的节点。划分清楚这两者什么时候同步、什么时候不同步是整道题的题眼。用虚拟头节点包裹之后pre 的初始值是 dummy而不是 head于是整个遍历过程中删除任何节点的动作都是一模一样的代码分支没有任何特殊情况。如果不用虚拟头节点你还得先想办法让 head 跳到第一个不等于 val 的位置然后再初始化 prehead、curhead.next。那样写不是不行而是每次读代码都要格外小心生怕把头节点那一段逻辑漏了。我自己刷题的经验是能在操作前加一层“统一外壳”就不给自己留特殊分支的机会。虚拟头节点就是链表的统一外壳。2.4 操作时间与空间的硬性指标复杂度分析这道题的时间复杂度是 O(n)n 是链表长度因为每个节点都被遍历了一次。空间复杂度是 O(1)除了几个指针变量外没有额外申请空间。这属于链表的常规操作水平面试时建议主动说出来。很多人在复杂度分析上有个误区觉得虚拟头节点多申请了一个节点空间复杂度不应该是 O(1)。其实不对申请单个固定大小的节点是常数级空间复杂度分析里依然记作 O(1)。只有申请了和输入规模成正比的空间才会记作 O(n)。3. 反转链表一次把方向改到底反转链表是LeetCode第206题也是所有链表题里地位最“基础中的基础”的一道。说它基础是因为迭代解法只需要三个指针说它重要是因为递归解法涉及对递归边界和“返回值是谁”的深刻理解理解透了之后能直接迁移到反转前N个节点、反转区间、K个一组反转等一堆问题。题目内容给定一个单链表的头节点 head反转链表返回反转后的新头节点。3.1 迭代反转pre、cur、temp 三个指针的接力迭代反转的核心思想特别朴素把每个节点本来指向后一个节点的 next 指针改成指向前一个节点。问题在于一旦你把 cur.next 改了cur 原来指向的下一个节点就找不到了所以你得提前用一个临时变量把它存下来。def reverseList(head: ListNode) - ListNode: pre None cur head while cur: temp cur.next cur.next pre pre cur cur temp return pre顺序特别重要先保存再改指最后移动。丢失引用的根源就是顺序写反。只要先存了 temp后面怎么改 cur.next 都不用怕。这里有两个必须自己想明白的点说实话也是面试官最爱追问的点第一个为什么 pre 的初始值是 None而不是 head 或者别的什么东西因为反转之后原来的头节点要变成新的尾节点它的 next 必须指向 None所以第一个处理节点时它的 next 就要指向 None也就是 pre 的初始值。第二个为什么最后返回的是 pre循环退出时 cur 已经变成 Nonepre 指向的是最后一个被处理的节点也就是原链表的尾节点。反转之后它就是新链表的头节点。如果你返回 head那只是回到了原链表的尾节点上去白忙一场。我一个很直观的建议是拿一支笔画四个节点从头开始一步步执行这段代码把每一个循环迭代里 pre、cur、temp 各指向谁标出来。画完三个迭代你就会发现这个算法的本质就是一条“传送带”temp 拎住后面的链条pre 和 cur 分别往前滚动同时把方向扭过来。3.2 递归反转换个视角“后面的已经反转好了”递归解法的切入点和迭代完全不同。迭代是从头开始一个个改变 next 的方向递归是想办法先走到链尾然后从后往前改变方向。def reverseList(head: ListNode) - ListNode: if head is None or head.next is None: return head new_head reverseList(head.next) head.next.next head head.next None return new_head第一次看到这段代码的人最难接受的是这一行head.next.next head。它的意思是让 head 的下一个节点的 next 反过来指向 head。注意这里的 head 是当前节点的名字不是整个链表的头节点。在递归的某一层里head 可能是中间某个节点。我建议用“后面的已经反转好了”这个视角来理解。reverseList(head.next) 被调用之后它会返回一个已经反转好的链表的头节点。打个比方你面前有一串项链你想把它整体倒过来。现在你只需要处理最前面的那一颗珠子它现在还指着第二颗珠子而第二颗珠子因为后面的都反转完了正好成了“后半段反转链表的尾节点”。你把第二颗珠子的 next 指向第一颗珠子再把第一颗珠子的 next 置空整个项链就倒过来了。递归的边界条件也值得拆一下。head is None处理空链表head.next is None处理只有一个节点的链表。这两种情况都是直接返回 head。只有这两个边界才意味着“不需要再反转了”。3.3 迭代与递归的取舍对照很多人会纠结考试时要写哪种。我的建议是练到两种都会面试时按需选。两种解法各有各的脾气。维度迭代法递归法空间复杂度O(1)O(n)递归栈会占用空间理解难度指针步骤直观画图即懂需要相信“后面的已经反转好”代码量略长极短适合场景大多数面试实操展示对递归的理解时可以秀一把如果你刷题起步不久我建议先死磕迭代因为它是所有指针操作的祖传基本功。递归版可以等迭代版能闭眼写了之后再拿它加深对递归的理解。两道都会写才是真的通。4. 从模板题到变式怎么把套路用到新题上像“移除链表元素”和“反转链表”这种题练完之后真正的价值在于你能不能用同一套底层动作去解决它的变式。下面我挑几个高频变体说明模板题是怎么被改造的。4.1 反转类变式前N个节点和区间反转反转整个链表学会之后最常见的变式是“反转链表的前N个节点”和“反转链表区间[m, n]”的节点。前者要求只反转前N个后者要求只反转中间一段。它们的共同点是反转操作本质上还是那三个指针的接力只是边界和收尾方式需要额外记录。拿区间反转来举例。假设链表是1-2-3-4-5要反转 2 到 4 这三个节点结果是1-4-3-2-5。这里的做法分三步先走到第 m-1 个节点这个位置叫 pre然后用迭代反转的手法把 pre 后面那一小段的方向改过来最后把这一段的前后接缝缝合好。处理接缝时你至少要提前记录两个节点pre 和原来 pre 的下一个节点也就是反转后这一段的尾节点。这个类型LeetCode第九十二题面试考频不低。从“反转整个链表”到“反转前N个”的递归版本也很有意思。你只需要在递归边界上做一个特殊处理反转前N个节点时当递归深度到第N个节点时要先把第N个节点原本指向的下一个节点记录下来作为整个新链表和后半段之间的“接线点”。很多人第一次做这道题会卡在这里因为标准全量反转时head.next 可以直接置空但反转前N个时不能置空要接到剩余部分上。4.2 删除类变式去重与按值删除“移除链表元素”的变式中最常见的是“删除排序链表中的重复元素”。比如1-1-2-3-3删完之后是1-2-3。这类题比按值删除更简单因为链表是排序过的重复元素一定连在一起。你只需要遍历时比较 cur.val 和 cur.next.val相等就跳过那一个节点不相等才移动 cur。另一种变式是“移除未排序链表中的重复节点”这种需要借助哈希集合记录已经出现过的值。思路就是把“按值删除”和“去重”结合在一起遍历的时候如果当前值出现过就删除没出现过就在集合里标记一下并移动 pre。有了虚拟头节点的基本功这种题写起来会顺手很多。还有一道很有代表性的合并题——“合并两个有序的单链表”。它考察的其实是“在正确的位置插入节点”的能力和删除、反转虽然动作不同但底层的“保引用”原则一模一样当你把一个节点从链表A上摘下来接到结果链表上时必须先保存好这个节点在A上的下一个节点位置否则A的剩余部分就丢了。说到“循环单链表”它是单链表的一种变体最后一个节点的 next 不指向 None而是指回头节点。它的问题套路也往往围绕“判断链表中是否有环”“找到环的入口”展开。基础的反转和删除原则在那里同样适用只是边界判断从“cur is None”变成了“cur 绕一圈回来”。你如果现在把普通链表的删除和反转吃透了以后接触循环链表和心理上的摩擦力会小很多。4.3 链表题的共同底层动作改指针前先备份我观察过很多人的刷题轨迹发现一个规律链表题做多了之后大家下意识会做的一个动作就是——看到 next 被赋值就先问自己“原来的引用丢了没”。这个动作几乎能概括链表题的一半功力。删除节点要保 pre.next反转链表要保 cur.next插入节点要保后一个节点合并链表要保两个链表的剩余部分……所有操作的共同底层逻辑都是这套“先备份再改指向最后移动”的心法。你甚至可以把它当成一个口诀来背改前先备份改动要连看move 前再确认。这个口诀虽然不严谨但对初学阶段的人来说比任何高深理论都管用。5. 最后说点刷题阶段的实在话这两道题代码量都很小但如果你只看答案不练习爆发的机会基本没有。我见过太多人在白板上写反转链表时前面写得挺顺到了第三行开始犹豫到底是先改 cur.next 还是先动 pre一旦开始犹豫面试官基本就能判断你对链表操作还不够敏感。5.1 循环不变量让代码一写就对的秘密武器我真正觉得帮到我的是一个叫“循环不变量”的思维工具。听起来很玄其实就是一句话在每一轮循环开始之前当前这几个指针分别处于什么状态把这个状态定义清楚了循环体里每一步都是在维持这个状态。拿反转链表来说每一轮循环开始前pre 指向的就是“已经反转好的新链表的尾节点”cur 指向的是“当前要处理的节点”temp 在循环体内保存 cur.next。只要你确信“进入循环前 pre 和 cur 各是谁、出去时应该变成谁”整个算法的正确性就立住了。写代码的时候心里揣着这个不变量就不太会出现那种“逻辑大体对但边界跑飞”的问题。递归解法也一样。递归版的不变量是“reverseList 接收一个参数 head返回一个以 head 为原头节点的链反转后的新头节点。”有了这个契约你才敢放心地调用 reverseList(head.next)然后在此基础上处理 head。5.2 特殊用例自测清单我每次写完链表代码不管多简单都强制自己过一遍这组测试用例。也推荐给你拿去当自测清单空链表head 是 None看代码能不能直接返回。单节点链表只有一个节点删除或反转后有没有问题。所有节点都要删除比如全是目标值看循环会不会把 head 一路移动到 None。头节点被删除头节点的值正好是目标值检查虚拟头节点有没有帮上忙。删除后连续删除比如目标值在链表中间连续出现了好几个检查 pre 不动但 cur 持续后移的情况。反转后尾部指向反转完成后新链表的最后一个节点 next 是不是 None。这组用例花不了多少时间但能帮你挡掉绝大多数低级错误。千万不要觉得代码能过一次测试用例就万事大吉链表的边界情况往往藏在“看似正确”的回显里。5.3 我的个人体会我个人刷链表题最大的体会是链表操作这种东西本质上是一场“保存引用”的杂技。你手上能握住的指针数量是有限的所以每一步都要想清楚哪些引用是临时的、哪些引用是最终要留下来的。写完这两道题你可以做一个练习不看任何资料在一个空白编辑器里把 removeElements 和 reverseList 从零开始写一遍每写一步注释一句话说明当前这一步背后维持的是什么状态。然后跑一下那些特殊用例看看哪里会挂。多数人第一次做这个练习时会发现自己以为懂了的地方其实还有一两个细节没打通。我第一次真正感到“链表通了”是连续三天每天晚上手写一次反转链表写完之后再画图核对每一步。第三天开始看到任何链表题脑子里的第一反应不再是“背代码”而是“改哪个 next、先保哪个引用”。这种感觉一旦建立后面再做链表相关的题目基本就进入顺风局了。