算法复健 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 用 <= size，delete 用 < size，这个一致性非常重要。
6. 实操心得：链表复健的节奏与后续安排
刷完这三道题，我最大的感触是：链表题不是比谁思路新颖，而是比谁能在细节上不出错。你完全可以用画图解决绝大多数困惑——在纸上画节点、画指针、模拟每一步移动。别嫌麻烦，画完再写代码，效率反而高出很多。
关于练习节奏，我建议你第一天只做 LC 203，把它和虚拟头节点吃透；第二天做 LC 707，把设计链表的五个方法写得滚瓜烂熟；第三天再做 LC 206，先迭代再递归。一天三题看似效率高，但对新手来说容易消化不良，还是分步来比较稳妥。
这三题之后，链表部分还有几道经典的延伸题值得安排进后续复健计划：删除链表倒数第 N 个节点、合并两个有序链表、环形链表检测、两两交换链表中的节点、链表排序等。它们本质上都是今天这三大基本功（删除操作、插入设计、反转思路）的变体。
我个人会在 Day4 先刷“删除链表倒数第 N 个节点”和“环形链表 II”，因为这两道题对快慢指针的运用很经典，能帮我把链表题的思维从“单指针挪动”升级到“双指针协作”。如果你也正在复健，建议按照自己的节奏来，不用贪多，每天两三道，把题吃透比刷过重要得多。
