LeetCode链表题精讲：移除元素、设计链表、反转链表

算法复健 Day3——链表三连移除、设计、反转把基本功焊死前两天的复健我刷了数组和二分说实话找回了一点点手感但真正让我意识到自己有多生疏的是今天这三道 LeetCode 链表题LC 203、LC 707、LC 206。链表这个东西你看着简单无非就是节点里存个值、存个指针但真上手写代码空指针、断链、边界条件一个接一个冒出来。今天这一篇我就专门把这三天里最值得掰开揉碎讲的三道链表题做一次完整复盘把虚拟头节点、指针移动、递归反转这类核心思路讲透顺带把我踩过的坑和排查经验全部放出来给正在刷题或者准备面试的朋友做个参考。这三道题其实是一条递进线LC 203 是最基础的链表删除帮你建立“操作链表必须管好前后指针”的潜意识LC 707 是让你手写一个完整链表类把查、插、删全部自己实现一遍特别考验对边界条件的敏感度LC 206 则是经典的反转链表循环和递归两种写法各有利弊值得反复手推。不管你是刚准备秋招、在复健数据结构的在职党还是纯粹想重新打一遍算法基础今天这篇都适合你。1. 整体思路为什么链表是算法复健必刷项1.1 链表和数组到底差在哪很多人刷题喜欢先挑数组和字符串因为看着直观但这恰恰是个误区。数组是一片连续内存随机访问 O(1)可插入删除要搬动元素链表恰好反过来不连续存储靠指针串联插入删除只要改指针 O(1)但查找必须从头遍历 O(n)。这个差异决定了实际工程里两种结构各有主场。更重要的是链表题写的是“指针操作”考的却是“思维缜密度”。一个节点有前驱有后继你改动一条指针是否照顾到了另一条指针节点被删除后内存是否需要主动释放这些细节在大厂面试里经常被追问而只有亲手实现过链表的人才能答得上来。我复健链表时给自己定了一个目标不看题解把以下三个操作全部手写出来——删除指定值节点、实现一个能增删查的链表类、反转整个链表。这正好对应今天的三道题。它们看起来简单但组合在一起几乎覆盖了链表题中 80% 的套路基础。1.2 三道题如何构成一条递进链LC 203“移除链表元素”是入门级它的价值在于让你学会“去除头部节点的特殊处理”也就是虚拟头节点dummy node的引入。LC 707“设计链表”直接升级为综合应用你必须自己维护链表结构并处理头插、尾插、任意位置插入删除这些边界密集的操作。到了 LC 206“反转链表”难度再次上升需要你理解指针指向的不断变化并且掌握迭代与递归两种思路。这三题刷下来相当于从“我会遍历链表”进化到“我能设计链表”再到“我能反转链表”。如果你能在一小时内独立完成并通过全部测试用例那么链表这块的基本功就算过关了。2. LC 203 移除链表元素虚拟头节点初体验2.1 题目看清再动手删的是全部匹配节点题目要求从一个单链表中删除所有节点值等于给定 val 的节点。注意“所有”这两个字意味着目标值可能出现多次、可能连续出现也可能出现在头部。核心难点就在头部节点——因为没有前驱删除头部需要特殊处理而很多新手的第一版代码恰恰在这里开始失控。我第一次写这题时按照最直觉的方式分情况讨论先处理头部再处理中间。代码确实能过但逻辑分支多容易遗漏。比如连续两个头节点都要删while 循环就得写对删完头部之后新的头节点恰好也是目标值的情况也必须考虑。这些分支一多人就容易绕晕。2.2 虚拟头节点的魔力让头节点和普通节点一样虚拟头节点的思路特别朴素在最前面加一个不存实际数据的节点它的 next 指向真正的头节点。这样一来原本没有前驱的头节点也有了统一的前驱删除逻辑可以完全一致。ListNode* removeElements(ListNode* head, int val) { ListNode* dummy new ListNode(0); // 虚拟头节点值随便 dummy-next head; ListNode* prev dummy; ListNode* cur head; while (cur ! nullptr) { if (cur-val val) { prev-next cur-next; // 跳过 cur delete cur; // C 手动释放内存 } else { prev prev-next; // 前驱跟着走 } cur prev-next; // 始终指向当前待判断节点 } ListNode* newHead dummy-next; delete dummy; return newHead; }关键点在于 prev 指针的移动时机。删掉节点时prev 不能动因为新的 prev-next 已经被赋值为 cur-next下一次循环要接着判断这个新节点只有没删除时prev 才向前移动。这个思维模式几乎可以套用到所有链表删除类题目。2.3 不带头节点的版本为什么更容易出错我也把不带头节点的版本写了出来作为对照学习用ListNode* removeElements(ListNode* head, int val) { while (head ! nullptr head-val val) { ListNode* tmp head; head head-next; delete tmp; } ListNode* cur head; while (cur ! nullptr cur-next ! nullptr) { if (cur-next-val val) { ListNode* tmp cur-next; cur-next cur-next-next; delete tmp; } else { cur cur-next; } } return head; }你能明显感觉到处理头节点的那段 while 循环是额外逻辑。如果头节点被删了新的 head 又要重新判断这个“惯性思维”特别容易断。所以我在给初学者讲这道题时会直接建议用虚拟头节点少写分支思路清爽代码正确率也高。2.4 复杂度与后续启发时间复杂度 O(n)空间复杂度 O(1)。虽然是入门题但这里面的虚拟头节点思路在后续很多题目中都会复用比如删除链表倒数第 N 个节点、合并两个有序链表甚至反转链表时都可以搭配使用。3. LC 707 设计链表手写一个类边界条件全暴露3.1 题目是一套组合拳查、头插、尾插、任意插、删LC 707 要求实现 MyLinkedList 类包含 get(index)、addAtHead(val)、addAtTail(val)、addAtIndex(index, val)、deleteAtIndex(index) 五个方法。看起来都是链表基础操作但组合在一起几乎任何细微错误都会导致测试失败。这道题最大的价值不是让你炫技而是强迫你认真考虑“索引”的含义。这里的索引从 0 开始get(0) 返回头节点值addAtIndex 的含义是如果 index 等于链表长度则插入到尾部如果 index 大于链表长度则直接忽略这次插入index 小于等于 0 则插入到头部。这里有个非常隐蔽的细节addAtIndex 的合法条件是 index size而 deleteAtIndex 的合法条件是 index size。我见过太多人在这两个条件上栽跟头一错就是一大片用例失败。3.2 类内部结构带不带头节点是核心决定实现上我依然推荐使用虚拟头节点同时维护一个 size 变量这样几乎所有操作都能统一处理。size 变量是必须的因为题目里要求链表的长度判断如果每次都遍历去数节点数既不优雅也容易出错。class MyLinkedList { private: struct Node { int val; Node* next; Node(int v) : val(v), next(nullptr) {} }; Node* dummy; int size; public: MyLinkedList() { dummy new Node(0); size 0; } int get(int index) { if (index 0 || index size) return -1; Node* cur dummy-next; while (index--) { cur cur-next; } return cur-val; } void addAtHead(int val) { Node* newNode new Node(val); newNode-next dummy-next; dummy-next newNode; size; } void addAtTail(int val) { Node* cur dummy; while (cur-next ! nullptr) { cur cur-next; } cur-next new Node(val); size; } void addAtIndex(int index, int val) { if (index size) return; // 注意这里是 index size 时合法 if (index 0) index 0; Node* prev dummy; while (index--) { prev prev-next; } Node* newNode new Node(val); newNode-next prev-next; prev-next newNode; size; } void deleteAtIndex(int index) { if (index 0 || index size) return; // 注意这里是 Node* prev dummy; while (index--) { prev prev-next; } Node* tmp prev-next; prev-next prev-next-next; delete tmp; size--; } };这里我特别想说一下 addAtTail 的写法。有人会额外用一个 tail 指针来维护尾部从而让尾插变成 O(1)。但那样做的话每次头插、删除尾节点都需要同步更新 tail很容易出错。对于这道题我认为直接遍历到尾部再插入是更稳妥的做法——毕竟没有性能上的硬性要求保证正确性优先。3.3 各方法的易错点和细节技巧get 方法里我用了 while (index--) 这样的写法每次 index 先自减再判断循环条件结合题目里 get 的 index 是从 0 开始这样写逻辑上正好。你如果觉得容易混也可以统一用 for 循环效果一样关键是保持一致。addAtIndex 是我觉得这题最有价值的处理。当 index 为 0 时prev 就是 dummy插入逻辑和 addAtHead 完全一样当 index 等于 size 时prev 会恰好落在末尾节点上插入后节点变成新的末尾节点。这一整套流程的第一反应可能不是直觉但是画图之后就很清晰了。deleteAtIndex 的边界同样需要留意。因为我的代码里所有定位都用了 index 自减所以 delete 时传入 index 0 表示删除头节点只要 dummy-next 不为空prev-next prev-next-next 就能正确跳过。整个类唯一的隐患就是 new 出来的 Node 一定要在析构函数里清理否则内存泄漏。3.4 关于内存管理的提醒这道题我没在类里写析构函数但实际工程中如果链表节点是 new 出来的析构函数必须遍历链表逐个 delete。这是 C 和 Java、Python 不一样的地方也是一些公司面试时喜欢追问的考点。虽然刷题时测试环境可能不在乎但这个习惯值得养成。4. LC 206 反转链表迭代与递归双重拆解4.1 题目核心指针方向全面反转反转链表要求把 1-2-3-4-5 变成 5-4-3-2-1。看着简单但第一次写的朋友十有八九会“断链”——比如把 cur-next 改掉之后原来的下一个节点就找不到了。所以这道题的关键不是“要不要反转”而是“反转时如何不让链表断掉”。我的建议是先画图。画出 1、2、3 三个节点模拟三根指针 pre、cur、tmp 一步步走特别要注意的是 tmp 的保存时机。这一点解决了迭代法基本就拿下了。4.2 迭代法三指针走天下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; // 循环结束时 prev 是新头 }这段代码的入口点在于 tmp 的保存。如果不先保存 cur-next执行 cur-next prev 之后原来的后继就丢了。三指针的移动顺序可以总结成一句口诀“先存后改再移 prev最后移动 cur。”我每次写都会心里默念一遍避免指针乱飞。4.3 递归法代码短但理解绕递归法很多人看着头皮发麻核心理解是这样的reverseList(head-next) 先把从第二个节点开始的子链表反转好返回的值是反转后子链表的头节点此时原来的 head-next 变成了反转后子链表的尾节点。接下来只需要把 head 接到这个尾节点后面并且把 head-next 置空即可。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 这一句的含义。当递归回到这一层时head-next 已经是指向原链表中 head 的下一个节点而由于子链表被反转head-next-next 原本指向的更后面的节点已经反转成新的尾节点了。现在我们让 head-next-next 指向 head就把 head 也接到反转子链表的尾部整个子链表完成反转。递归的复杂度同样是时间 O(n)、空间 O(n)因为递归调用栈会占用 O(n) 的额外空间。实际工程中更推荐迭代法但面试时你能把递归写出来往往是一个加分项至少说明你对函数调用栈有感觉。4.4 递归 vs 迭代怎么选我个人的建议是先把迭代法写到肌肉记忆能默写出来为止然后单独找时间把递归法手推三到五遍直到能不看代码复原。迭代法的好处是空间 O(1)、不容易爆栈递归法的好处是代码简洁、逻辑统一。面试时如果时间紧张我一般先写迭代再把递归作为“能补充的点”提出来。5. 常见问题与排查技巧实录5.1 链表题最常踩的四类坑我这次复健踩了不少坑把最典型的四类问题整理成了一张表方便你自查。症状根因解决方法访问了空指针的 next 或 val没判断 cur nullptr 就直接取节点属性进入循环前先判空使用 prev-next 代替 cur 做判断链表成环打印时死循环反转或删除时某个节点的 next 没有正确置空画图检查每一步指针指向反转最后记得 head-next nullptr删除节点后访问已释放内存直接将 cur 指针释放但后续仍被引用先保存 tmp cur-next再释放或者仅用 prev 操作不持有待删节点指针边界用例失败比如只有一个节点没有覆盖 size 1 或 index 0 的情况单独列出边界条件编写测试用例逐一验证这四个坑每一个我都真实踩过尤其是第二个“成环”。有次我在做反转链表练习时忘掉把原头节点的 next 置空结果本地打印链表直接死循环最后靠打印节点值数量才发现问题。所以写完之后第一件事不是提交而是先用几个手写用例在本地过一遍。5.2 一个通用的调试技巧打印链表链表题调试的核心方法就是打印。你可以自己写一个辅助函数把链表从头到尾打印出来每操作一步都看一眼结果void printList(ListNode* head) { ListNode* cur head; while (cur ! nullptr) { cout cur-val - ; cur cur-next; } cout null endl; }在迭代反转时我会把每次循环后的链表状态都打印一遍这样能直观看到指针是否都在正确的位置。LC 707 设计链表时更是要在每个方法调用之后打印比如 addAtIndex 之后立即打印整个链表确认插入位置对不对。相信我这比盯着代码干想快得多。5.3 一些“看不见”的细节虚拟头节点的值可以随便设置因为它的 val 永远不会被访问到但为了代码可读性还是设成 0 比较好。C 用 new 创建的节点记得 delete避免内存泄漏。刷题时测试环境不一定会管但面试官可能追问。写递归时一定要有递归出口否则栈溢出。链表递归的出口通常是 head nullptr || head-next nullptr。如果所有操作用的是 index 变量请统一边界add 用 sizedelete 用 size这个一致性非常重要。6. 实操心得链表复健的节奏与后续安排刷完这三道题我最大的感触是链表题不是比谁思路新颖而是比谁能在细节上不出错。你完全可以用画图解决绝大多数困惑——在纸上画节点、画指针、模拟每一步移动。别嫌麻烦画完再写代码效率反而高出很多。关于练习节奏我建议你第一天只做 LC 203把它和虚拟头节点吃透第二天做 LC 707把设计链表的五个方法写得滚瓜烂熟第三天再做 LC 206先迭代再递归。一天三题看似效率高但对新手来说容易消化不良还是分步来比较稳妥。这三题之后链表部分还有几道经典的延伸题值得安排进后续复健计划删除链表倒数第 N 个节点、合并两个有序链表、环形链表检测、两两交换链表中的节点、链表排序等。它们本质上都是今天这三大基本功删除操作、插入设计、反转思路的变体。我个人会在 Day4 先刷“删除链表倒数第 N 个节点”和“环形链表 II”因为这两道题对快慢指针的运用很经典能帮我把链表题的思维从“单指针挪动”升级到“双指针协作”。如果你也正在复健建议按照自己的节奏来不用贪多每天两三道把题吃透比刷过重要得多。