链表算法刷题实战：移除元素、设计链表与反转链表核心技巧

今天训练营第三天三道题全部集中在链表上203移除链表元素、707设计链表、206反转链表。相比前两天的数组题目链表这部分最大的特点是考验“指针操作”的细腻程度很多同学在数组题上写起来很顺一到链表就各种空指针、死循环、改丢节点。今天这三道题恰好把链表操作里最核心的几个场景全部覆盖了一遍处理完这一套后面再做链表相关的题会顺手很多。先说明白今天的内容适合谁看刚学完链表基础、想通过题巩固指针操作的人刷题时经常在边界条件上翻车的人也包括面试前想快速把链表常见操作捋一遍的人。三道题难度都不算高但细节密度很足把思路讲透比直接贴代码更有价值。1. 整体思路拆解这三道题放在一起练什么1.1 三道题其实是链表操作的三块基石刷题最容易犯的毛病是孤立地看每一道题觉得“这题我过了就行”。但代码随想录把这三道题放在第三天是有内在逻辑的拆开看它们分别对应链表最核心的三个能力。203移除链表元素练的是“遍历链表并在合适位置删除节点”这是所有链表修改操作的地基。删除操作不是某一种特定题型的专利像有序链表去重、删除倒数第N个节点、删除排序链表中的重复元素本质上都是同一套动作。能把203写利索后面遇到同类题思路几乎是平移过去的。707设计链表练的是“从零到一实现一个链表的完整API”。这道题不是让你解一个算法问题而是让你自己设计链表类的内部结构并实现增、删、改、查等全套操作。它考察的不只是某个操作而是你对索引、边界、节点指针关系的整体把握。很多人在写单题时勉强能过一旦要求把所有操作打包成一个类就开始漏边界。707就是专门治这个毛病的。206反转链表练的是“指针方向的整体扭转”。它看起来简单其实非常考验对“保留后继节点”这个动作的理解。反转的过程就是不断修改next指向的过程但每改一个节点的next之前必须先把它原本的next存下来否则链表就断了。这个“先保存再修改”的习惯在做链表排序、链表重排等问题时都是必须的。1.2 链表和数组的差异决定了做题方式不同做数组题时我们可以随意通过下标访问任意元素因为数组的内存空间是连续的。链表不同它的节点在内存中是分散的只能通过每个节点的next指针一个一个找下去访问第index个节点必须从头遍历复杂度O(n)。这个差异带来一个核心习惯操作链表时脑子里要有指针移动的过程画面。不要只盯着代码看而是想清楚当前指针走到哪了、它指向的节点的next是谁、操作完之后还有没有指针指向这个节点。我在训练营带大家写题时经常说一句话链表题如果丢节点要么是没保存后继要么是指针移动顺序错了。另外链表题里“虚拟头节点”是一个极其常用的技巧。删除头节点时需要特殊处理因为头节点没有前驱。但如果我们人为构造一个dummyHead让它的next指向真正的头节点那么整个链表就统一了每个需要删除的节点都有前驱节点不再需要区分“删头节点”和“删中间节点”逻辑会清爽很多。2. 203.移除链表元素头节点的删除逻辑是第一个坎2.1 题目拆解与测试用例设计203题要求删除链表中所有节点值等于给定值val的节点。听起来很简单但难点在于如果头节点的值就等于val你要怎么处理举一个最极端的例子链表是7-7-7-7val是7。这种情况下删除之后链表应该为空。如果你没有处理头节点的逻辑第一次删除就把链表删空了继续操作就容易出现空指针访问。再比如7-7-8-7val是7这种“头部门连着删两个”的场景也很容易在指针移动时漏掉第二个重复。我建议大家做题之前先自己设计几组用例跑一跑思路空链表、头节点就是目标值、连续多个目标值、目标值在尾部、中间有目标值但不连续。每组用例都能帮你发现一类边界问题比直接看题解更有效。2.2 两种解法的对比直接删除与虚拟头节点先看最朴素的做法分两种情况讨论。如果头节点需要删除就让head不断后移直到head为空或head的值不等于val处理完头部之后再用一个cur指针从新的头节点开始遍历遇到cur-next的值等于val就把cur-next指向cur-next-next。这个写法本身没有错但问题在于“分情况讨论”这恰恰是容易出bug的地方。比如你处理完头部之后链表可能已经变成空链表了后面遍历时要加空指针判断再比如head移动到新位置后如果新的头节点也等于val中间要用while循环而不是if。细节一多出错概率就上来了。虚拟头节点法就不一样。我们new一个dummyHead节点让它的next指向head然后只用一个cur指针从dummyHead开始遍历。每次检查cur-next的值如果等于val就删除否则cur后移。整个过程不需要再关心头节点这个特殊角色因为虚拟头节点永远充当了头节点的前驱节点逻辑统一结构简单。删除完成后返回dummyHead-next就是新链表的头节点。可以用一个生活中的例子来理解直接删除法相当于你是一个巡警发现队伍第一个人是坏人时要先让整个队伍重新排队再继续巡逻虚拟头节点法相当于你给自己加了一个“观察员”身份永远站在队伍外面观察队首和第一个人不管第一个是谁都不会搞乱自己的位置。2.3 代码实现与易错点分析用虚拟头节点写C代码如下ListNode* removeElements(ListNode* head, int val) { ListNode* dummyHead new ListNode(0); dummyHead-next head; ListNode* cur dummyHead; while (cur-next ! nullptr) { if (cur-next-val val) { ListNode* tmp cur-next; cur-next cur-next-next; delete tmp; } else { cur cur-next; } } return dummyHead-next; }Python版本同样思路def removeElements(self, head: ListNode, val: int) - ListNode: dummy_head ListNode(nexthead) cur dummy_head while cur.next: if cur.next.val val: cur.next cur.next.next else: cur cur.next return dummy_head.next这个代码有几个地方值得停一下。首先cur指针只有在没有删除操作时才往后移动这一点很容易写错。如果每次循环都让cur后移一旦删除后cur-next已经是下一个节点你再把cur往后挪一位就会跳过刚才的那个新节点导致它没被检查到。很多人写这个题出现“漏删”就是这个问题。其次删除节点后要注意内存释放。C里用tmp保存被删除节点的指针然后delete防止内存泄漏。C面试的时候内存管理是很看重的点刷题时养成好习惯后面做项目也不会因为malloc/new和delete/free对应不上而头疼。最后是返回值无论哪种写法最终都要返回新链表的头节点。用虚拟头节点时直接返回dummyHead-next不要返回head因为head可能已经被删掉了。3. 707.设计链表把链表的API整体实现一遍3.1 需求分析与数据结构设计707题要求实现一个链表类MyLinkedList包含get、addAtHead、addAtTail、addAtIndex、deleteAtIndex这几个方法。括号里还说明了index从0开始并且要支持“单向或双向链表”这类题我建议做单向即可除非你特别想要练习双向。这个题的精髓不在于某个方法单独怎么写而是把几个方法整合在一起时怎么保证各类边界情况都不报错。我做完这个题最大的感受是你要对index、size这些属性有非常清醒的认识否则会在get(0)和addAtIndex(0, val)这种地方反复踩坑。我的设计选择是使用一个size变量记录链表长度再加一个虚拟头节点dummyHead也叫哨兵节点。size初始化为0dummyHead的next初始化为nullptr。为什么用虚拟头节点而不是直接用head因为addAtHead和delete头节点时如果没有虚拟头节点你需要单独处理“新节点变成头节点”“删除头节点后头节点要更新”等逻辑代码里全是if判断。有了虚拟头节点addAtHead就变成了在dummyHead后面插入节点delete一个节点也统一成了cur-next cur-next-next。整体的代码复杂度会低很多。需要特别留意的是size表示的是链表中真实节点的个数不包括虚拟头节点。我见过很多人把这个搞混导致get或addAtIndex时遍历的次数总是多一次或少一次。3.2 各方法的实现要点与索引边界逐个来看几个关键方法。get(int index)就是“判断index是否有效然后从头遍历到第index个节点”。首先做校验如果index 0或index size直接返回-1。然后从dummyHead-next开始循环index次每循环一次cur后移一位最后返回cur-val。这里有一个很经典的坑你要搞清楚循环几次才能到第index个节点。从虚拟头节点开始遍历要走index1步才能跳到索引为index的节点但因为你初始化时直接指向了第一个节点所以循环index次即可。这个“少走一步、多走一步”的问题是链表题里最常见的错误来源建议每次写循环前先画一下节点位置。addAtIndex(int index, int val)是这道题的灵魂方法。题目要求是在下标为index的节点之前插入新节点。如果index等于链表的长度则说明新节点追加到链表末尾如果index大于链表长度则不插入如果index小于0则插入到头部。实际问题里index小于0很容易被忽略但题目给了定义就要实现完整。实现上先处理特殊情况如果index size直接return如果index 0把index设为0当作头部插入处理。接下来用一个cur指针从dummyHead开始遍历index次使cur指向待插入位置的前驱节点。然后new一个新节点让新节点的next指向cur-next再让cur-next指向新节点最后size。这里的顺序很重要一定是先让新节点指向cur-next再让cur-next指向新节点。如果反过来先修改cur-next你原本的后继节点就丢了新节点后面的链表就断掉了。这一点是绝大多数链表插入题的核心考点无论是这道题还是后面要做的各种链表插入题顺序都不能变。addAtHead和addAtTail更简单直接复用addAtIndex就行头部插入是addAtIndex(0, val)尾部插入是addAtIndex(size, val)。当然也可以单独实现但复用addAtIndex的好处是只要你把addAtIndex写对了另外两个方法基本不可能出错。deleteAtIndex同样要先用index0 || indexsize做校验然后从dummyHead开始走到待删除节点的前驱节点执行cur-next cur-next-next释放被删节点的内存size--。3.3 完整代码实现与常见边界我给出一个C的完整实现你已经可以在本地直接运行class MyLinkedList { public: struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; MyLinkedList() { dummyHead new ListNode(0); size 0; } int get(int index) { if (index 0 || index size) return -1; ListNode* cur dummyHead-next; while (index--) { cur cur-next; } return cur-val; } void addAtHead(int val) { addAtIndex(0, val); } void addAtTail(int val) { addAtIndex(size, val); } void addAtIndex(int index, int val) { if (index size) return; if (index 0) index 0; ListNode* cur dummyHead; while (index--) { cur cur-next; } ListNode* newNode new ListNode(val); newNode-next cur-next; cur-next newNode; size; } void deleteAtIndex(int index) { if (index 0 || index size) return; ListNode* cur dummyHead; while (index--) { cur cur-next; } ListNode* tmp cur-next; cur-next cur-next-next; delete tmp; size--; } private: ListNode* dummyHead; int size; };这里有一个细节值得专门说明虚拟头节点不作为有效节点计入size所以在addAtIndex和deleteAtIndex中走到前驱的循环次数是index次而不是index1次。很多人写了半天不对往往就是size的语义与虚拟头节点没有统一。还有一个性能小问题addAtTail的实现如果直接addAtIndex(size, val)每次都要从头遍历时间复杂度O(n)。如果对效率有要求也可以维护一个tail指针让尾部插入达到O(1)。但作为刷题练习来说O(n)完全够用面试时如果你能主动提一句“可以用尾指针优化到O(1)”会是个加分点。4. 206.反转链表双指针法与递归法各有千秋4.1 反转的核心保留后继再改指向反转链表是链表题里最经典的一道没有之一。题目要求把1-2-3-4-5反转为5-4-3-2-1。很多第一次做的人会想“能不能新建一个链表然后从原链表尾部开始插入”理论上可以但空间复杂度是O(n)面试时一般不会满意。反转的本质是把每个节点的next指针方向调转。对于节点2原本next指向3反转后要让它指向1。问题在于当你把2-next改成1之后你就失去了3的地址后面的节点全都找不到了。所以正确做法是在修改cur-next之前先用tmp保存cur-next然后再执行反转操作。我用过一句话总结这个过程改一个节点的next前先抓住它原本的下一个。这个习惯任何链表修改操作都适用。4.2 双指针法步骤清晰不易写错双指针法处理反转链表非常直观。定义prev指针初始为nullptrcur指针初始为head。循环里做四件事先用tmp保存cur-next然后把cur-next指向prev接着prev移动到cur的位置最后cur移动到tmp的位置。循环结束时cur已经为空prev指向原链表的尾节点也就是新链表的头节点返回prev即可。C代码如下ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* cur head; while (cur ! nullptr) { ListNode* tmp cur-next; cur-next prev; prev cur; cur tmp; } return prev; }Python版本def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]: prev, cur None, head while cur: tmp cur.next cur.next prev prev cur cur tmp return prev整个过程可以用“排队转身”来类比想象一队人本来面朝右边队尾的人手里拿着一个气球现在要求每个人都转身面朝左边。每个人转身之前必须先把身后那个人的手拉住保存后继否则转身后身后那个人会被甩出队伍。prev和cur就是两个相邻位置的人prev在前一个位置cur在当前转身的位置tmp就是拉住的后面那个人。这个写法我推荐大家作为反转链表的首选因为循环结构清楚、变量少、不容易在递归的思路里绕进去。4.3 递归法理解栈的回到上一层递归法核心逻辑是反转以head为头节点的链表等价于先反转head-next为头节点的子链表然后把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; }这个过程可以结合栈来理解递归不断深入直到最后一个节点才返回然后在“归”的过程中每一步把当前节点接到它下一个节点的后面。比如链表1-2-3-4-5递归到5时返回回到4时让4-next-next 4也就是5-next 4再让4-next nullptr然后回到3让4-next 33-next nullptr。以此类推最终返回的newHead就是5。递归写法答起来很帅但有两个容易出错的地方。第一是终止条件要写全head为空或head-next为空都要返回。第二是在处理完head-next-next head之后一定要把head-next置为nullptr。如果不置空链表内部就可能出现环或者反转结果的头节点后面残留错误连接这在调试时非常难看出来。双指针法和递归法本质上是一回事递归只是把迭代过程藏进了函数调用栈。我建议两种都写熟练面试时哪个思路讲得顺就用哪个。但如果只求稳双指针法更容易控制。5. 高发问题与排查技巧三天链表实弹经验总结5.1 空指针访问与死循环是两大头号问题链表题90%的bug可以归为两类一类是空指针访问另一类是死循环。空指针访问出现得最多的是这种情况循环里直接使用cur-next-val却没有先判断cur-next是否为空。比如在203题里如果你用cur从head开始遍历并且每次判断cur-next-val一旦链表中只有一个节点且它恰好等于val删除后cur-next就成了空指针下一轮循环再去访问cur-next-val就会直接崩溃。解决问题的办法就是每轮循环都先检查cur-next ! nullptr再访问它的值。死循环通常是因为指针移动条件写错。最典型的是206反转链表里如果你忘记保存tmp或者在修改next之后还继续使用cur-next程序就会在某个节点上原地打转。还有个常见误区是循环里的cur cur-next在删除操作后仍然执行导致跳过新指针看起来像“没有删除干净”细查之后发现其实是“跳过太多节点”。5.2 节点删除后务必释放内存C刷题时new出来的节点不释放会造成内存泄漏。虽然LeetCode的测试用例跑完就结束了内存泄漏的影响不明显但写到工程代码里这就是大问题。我在代码里用delete的时候会习惯性地先用一个tmp保存待删除节点的指针等指针的next关系调整完之后再delete。顺序不能反如果你先删了节点再想去取它程序直接崩溃。面试时如果面试官问“删除节点之后为什么还要delete”你要能答得清楚不delete的话这个节点从链表里摘出来却仍然占着内存程序长时间运行就会越占越多。平时刷题做好这一步也是一种刻意练习。5.3 索引与size语义混乱怎么办707里的索引问题是所有链表类题目的高频坑。概括起来就一句话index到底是指“移动几次”还是“到哪个位置”。我的做法是死死咬住“节点下标”的定义索引0是第一个有效节点不是虚拟头节点。遇到addAtIndex和deleteAtIndex这类需要找前驱的操作我习惯先画图。比如链表有5个节点要在索引3的位置插入那么cur应该移动到哪个位置答案是索引3对应的前驱是索引2的节点所以cur要从虚拟头节点出发移动3次指向索引2。这样想就不容易错。另外size的维护一定要跟每一步插入删除同步。707题里最好把size和size--放在最显眼的位置防止忘写。曾见过一个同学把addAtIndex写完后测试addAtHead再get(2)结果永远少一位查了半天发现是addAtIndex里忘记size了。5.4 常见问题速查表问题现象可能原因解决思路运行时报空指针错误未先判断cur-next是否为空就访问值循环体开头先检查cur-next是否为空链表少了一个节点删除节点后cur指针又额外多走一步删除时不移动cur未删除时才移动cur程序进入死循环修改next前没有保存后继节点用tmp先保存cur-next再执行指针修改反转后链表断裂递归时没有把head-next置空递归返回前设置head-next nullptrget(0)结果不对size跟虚拟头节点混淆确认size只统计有效节点addAtTail后链表末尾丢失addAtIndex循环次数算错用dummyHead开始走index步走完后停在待插入位置的前驱6. 刷完三道题之后你还能继续做什么如果你到今天为止这三道题都能在不看题解的情况下独立写完那你的链表基本功已经过关了。接下来的巩固方向我建议从两个维度展开。第一个维度是“变体练习”。203题学会了删除指定值可以顺手做83题“删除排序链表中的重复元素”、19题“删除链表的倒数第N个节点”206题学会了反转可以接着挑战92题“反转链表II”它要求只反转区间内的部分链表707题把API写完了后面做146题“LRU缓存”时你能感觉到对链表增删操作的理解明显比没做过707的人更深。第二个维度是“复杂度意识”。链表题面试时除了写对代码还要能够脱口而出时间复杂度查询是O(n)头部插入删除是O(1)尾部插入在维护尾指针时是O(1)否则是O(n)。这些复杂度分析不只是背结论它是你选择数据结构时的依据。很多系统设计题里产品要求频繁头部插入、偶尔随机访问这时候链表就比数组更合适原因正在于复杂度差异。还有一个小技巧我一直想分享刷链表题时可以准备一张草稿纸每道题动手写代码前先把链表画出来再把指针的变化过程画出来。不要觉得多此一举实测下来画图五分钟Debug省一小时。尤其是反转链表的题画完图你会发现自己写代码的准确率提升得非常明显。坚持到今天链表这个数据结构的基本功就算打扎实了明天训练营大概率会开始接触哈希表相关的内容那时候你会发现链表和哈希表经常配合在一起考比如“哈希链法”解决哈希冲突再比如很多LRU题目就是哈希表加双向链表。今天就先到这儿把三道题亲手写完、调试完链表这一关你就算真正迈过去了。