1. 先把链表底子打好：203、707、206这三题到底在练什么
代码随想录算法训练营第三天，题目排得很有意思：LeetCode 203移除链表元素、707设计链表、206反转链表。三题放在同一天，不是随便凑数，它们刚好覆盖了链表操作最核心的几个动作——删除节点、完整的增删查实现、指针方向反转。对刚开始刷链表的人来说，这一天如果一遍能过，后面遇到中等难度的链表题会顺很多；如果写得磕磕绊绊，那说明对“指针操作”的理解还停留在纸面上。这篇就把三道题的思路、代码和易错点展开讲清楚，适合正在跟训练营的读者，也适合任何想系统掌握链表基础操作的人。
1.1 节点与指针：链表的“寻宝游戏”
如果你第一次接触链表，别急着抄代码，先搞清楚它在内存里到底怎么存。链表的每个节点主要由数据域和指针域构成，在C++里通常写成：
struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} };val是当前节点存的值，next是指向下一个节点的指针。数组是一段连续内存，按索引可以直接访问；链表节点则分散在内存里，只能靠每个节点的next指针“顺藤摸瓜”。我之前带模拟项目X的同学时，见过不少人一上来就想把链表“转成数组”，操作完再“转回来”，简单题的答案能过，但一到设计链表、反转链表，或者后面的环形链表、排序链表，马上就露馅。因为链表真正的价值就在于“动态插入删除不需要移动大量元素”，你把这个优势丢掉，等于放弃了训练链表的初衷。
生活里有个很贴切的类比：数组就像电影院一排固定座位，找人就按座位号；链表就像寻宝游戏，每张纸条上写着下一个线索的位置。你要找到某个人，只能从第一张纸条开始一张张往下读。理解了这种“线索式”结构，再看虚拟头结点、反转链表这些操作，就不会觉得是在背魔法了。
1.2 三道题为什么是“铁三角”
我刷了这么多年题，回头看训练营第三天选的这组题，确实有讲究：
- 203移除链表元素是入门题，核心是“遍历加断链”，删除节点时的边界问题主要体现在头节点该不该特殊处理。
- 707设计链表把链表完整操作包装成一个类，从get到addAtHead、addAtTail、addAtIndex、deleteAtIndex，等于让你亲手搭一遍链表骨架。
- 206反转链表是经典题，把指针方向整体拧过来，迭代和递归两种解法都要会。
这三题按“看懂删除 → 会写完整类 → 能扭转指针”的顺序推进，刚好覆盖链表核心考点。后面常见的面试题，比如两两交换节点、删除倒数第N个节点，很多都是这三个基础动作的组合。哪怕你已经在力扣上刷过几十题，这三道依然值得重新写一遍，因为它们的细节密集度极大，尤其707，几乎能把链表所有坑一次踩完。
1.3 动手前先统一两个术语
看题之前，我建议先把两个容易混淆的说法理清楚。第一，“头指针”head指向链表第一个节点；有些实现会用一个“虚拟头结点”dummy，dummy不存有效数据，next指向真正的首节点。第二，力扣题里说的“第index个节点”默认从0开始，707题的接口定义就是这个意思，别被绕晕。统一了术语，后面写代码时就不会在边界判断上打架。
注意：有些在线测评平台会引入“头结点”和“头指针”的不同叫法，刷题时要先看平台自己的定义。虚拟头结点在链表题里几乎万能，但在面试手写时，要先和面试官确认题目期望，有些面试官特意想看你不开dummy时怎么处理头节点。
2. LeetCode 203. 移除链表元素：虚拟头结点是新手的第一道护身符
2.1 题目到底在问什么
203题的要求很直白：给你一个链表的头节点head和一个整数val，删除链表中所有满足Node.val == val的节点，返回新的头节点。比如链表是1->2->6->3->4->5->6，删掉所有6之后，结果应该是1->2->3->4->5。
注意“所有”两个字，意味着可能连续出现多个相同值，也可能头节点正好要删。如果一开始用：
while (head != nullptr && head->val == val) { head = head->next; }把头节点先清理干净，后面遍历删除就简单了。但这么写的坏处是：每道涉及删除的题都要单独考虑“头节点被删”的情况，代码不够统一。特别是当题目没有说明头节点会不会变化时，你会提心吊胆。与其每次临时判断，不如直接引入一个虚拟头结点。
2.2 为什么虚拟头结点能省掉一半边界判断
虚拟头结点的思路，就是先造一个dummy节点，让dummy->next指向原来的head。这样原来的头节点就变成了“dummy的下一个节点”，删除头节点和删除中间节点在逻辑上完全一致，不再需要特殊分支。
看标准解法：
class Solution { public: ListNode* removeElements(ListNode* head, int val) { ListNode* dummy = new ListNode(0, head); ListNode* cur = dummy; while (cur->next != nullptr) { if (cur->next->val == val) { ListNode* tmp = cur->next; cur->next = cur->next->next; delete tmp; } else { cur = cur->next; } } ListNode* result = dummy->next; delete dummy; return result; } };拆开讲几个关键点。
第一，cur的起始位置是dummy，不是head。因为我们要判断cur->next的值，cur必须停在待删节点的前一个位置。如果让cur等于head，head本身要被删除时就非常麻烦。
第二，找到待删节点后，不能顺手cur = cur->next。比如链表是1->2->2->3，要删2，cur停在第一个2之前时，执行cur->next = cur->next->next后，cur的下一个节点已经变成第二个2，此时cur必须保持不动，下一轮循环才能继续判断并删除。这个细节是漏删连续重复节点的最常见原因。
第三，C++题目中删除节点最好delete一下。在线判题环境即使不delete也能通过，因为后台会统一回收内存，但在面试或本地工程里，内存泄漏是很严重的问题。我会在代码里释放tmp，并且最后释放dummy，保证没有泄漏。
复杂度方面，每个节点最多访问一次，时间O(n)；只用了dummy和cur两个指针，空间O(1)。
2.3 不带头结点的写法与对比
如果不使用dummy，代码可以这样写：
class Solution { public: ListNode* removeElements(ListNode* head, int val) { while (head != nullptr && head->val == val) { ListNode* tmp = head; head = head->next; delete tmp; } if (head == nullptr) return head; ListNode* cur = head; 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 head; } };这段代码也能过，但你会看到，所有“删除头节点”的逻辑都集中到开头了，后面遍历时不需要再担心head。两种写法在核心思想上没有区别，真正的差别是代码结构：虚拟头结点版本把“保护头节点”这件事交由dummy统一处理，更适合套用到下一道题；非dummy版本则更贴近“链表原本结构”，有时候面试官会故意要求不额外创建节点。
我的建议很明确：新手先把dummy版本写熟，因为它提供了统一的删除模型。等dummy版本能秒写之后，再练习非dummy版本，两边的边界判断都能覆盖，面试时才不会慌。
2.4 这题常见的几个翻车现场
我把平时看到的高频错误列一下：
- 删除头节点后，最后返回的还是旧head，导致答案开头多一个已删除的节点。
- 删除非头节点时，没有把前驱节点的next接到后继节点上，链表直接断裂，输出少半截。
- 遇到连续重复值，删除第一个后cur向后移了，第二个重复值被跳过。
- 空链表没有判空，直接访问head->next，程序崩掉。
排查方法也很简单：把链表长度和每个节点的地址打印出来，看删除前后的next指向是否符合预期。很多时候眼睛盯代码半天看不出来，一打印就原形毕露。
3. LeetCode 707. 设计链表：把增删查完整实现一遍，才算真正会链表
3.1 先看清题目里的所有边界
707题要求设计一个MyLinkedList类，支持五个方法：
- get(int index)：获取链表中下标为index的节点值，无效返回-1。
- addAtHead(int val)：在头部插入一个值为val的节点。
- addAtTail(int val)：在尾部插入一个节点。
- addAtIndex(int index, int val)：在下标为index的节点前插入节点。如果index等于链表长度，插到末尾；如果index大于链表长度，不插入。
- deleteAtIndex(int index)：删除下标为index的节点，无效则不操作。
这里最容易忽略的是addAtIndex那句“如果index等于链表长度，则插入到末尾”。很多人以为必须小于size才能插入，结果把合法边界写没了。另外，size的维护是重灾区：插入后size加一，删除后size减一，这看起来简单，但在多方法连续调用的测试用例里，漏加漏减一次，get的越界判断就全乱了。
3.2 选单链表还是双链表
力扣官方题解里有双链表版本，因为支持addAtTail时双链表可以直接在tail指针前插入，效率更优。但707题的本质是练习，单链表完全能实现所有功能，复杂度也都是O(n)。我建议训练营第三天先用单链表加虚拟头结点做一遍，原因有两个：一是单链表只维护next指针，代码量更小，适合把“找前驱节点”的核心逻辑练透；二是后面遇到复杂链表题，大多数人还是要回到单链表思维。双链表的难点在插入删除时要同时维护prev和next，四个方向都要改，出错概率高得多。等单链表版本流畅了，再自己改成双链表，感受两种实现的差异。
3.3 结构设计与get方法
先定义类的基础：
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; } // 其他方法后续给出 };很多人在构造函数里忘了初始化size，默认是随机值，后面全乱。dummy节点也算一个“哨兵”，它不参与计数，size只统计有效节点。
get的循环从dummy->next出发，因为下标0对应第一个有效节点。走index步后，cur正好停在目标节点。这里用while(index--)是C++里常见写法，index等于0时循环体不执行，直接返回当前节点值。如果你更习惯for循环，写for (int i = 0; i < index; i++)也一样。
3.4 四个修改方法的完整实现
addAtHead：
void addAtHead(int val) { Node* newNode = new Node(val); newNode->next = dummy->next; dummy->next = newNode; size++; }这里顺序很重要：先把newNode的next指向原首节点，再把dummy->next指向newNode。如果先改dummy->next，原链表的头就丢了。
addAtTail：
void addAtTail(int val) { Node* cur = dummy; while (cur->next != nullptr) { cur = cur->next; } cur->next = new Node(val); size++; }addAtTail需要遍历到末尾，时间复杂度O(n)。如果追求效率，可以额外维护一个tail指针，但那样在删除尾节点时要处理tail回退，复杂度上升，不建议新手一上来就这么干。
addAtIndex：
void addAtIndex(int index, int val) { if (index < 0 || index > size) return; Node* cur = dummy; while (index--) { cur = cur->next; } Node* newNode = new Node(val); newNode->next = cur->next; cur->next = newNode; size++; }边界条件是index > size不插入，而不是index >= size。index == size时，上面的循环会把cur移到最后一个节点，然后新节点插到它后面，正好完成尾插。需要注意，调用addAtHead和addAtTail时其实都可以直接复用addAtIndex：addAtHead就是addAtIndex(0, val)，addAtTail就是addAtIndex(size, val)。不过自己单独写一遍，能更好理解每步操作。
deleteAtIndex：
void deleteAtIndex(int index) { if (index < 0 || index >= size) return; Node* cur = dummy; while (index--) { cur = cur->next; } Node* tmp = cur->next; cur->next = cur->next->next; delete tmp; size--; }删除时index等于size是非法操作，所以条件要写index >= size。循环结束，cur停在待删节点的前驱位置，然后执行经典的“跳过”操作。最后别忘delete和size--。
3.5 为什么get与addAtIndex的“起跑线”不一样
这是707题最容易被忽略的细节。get是从dummy->next开始走index步，因为我们要获取的是目标节点本身。而addAtIndex和deleteAtIndex是从dummy开始走index步，因为要插入或删除，必须先找到前驱节点。比如链表1->2->3，要在index=1前面插入新节点，前驱是下标0的节点，所以要走到它前面。这个差别也可以理解为“读位置”和“写位置”的差别。很多人在写addAtIndex时复用get的循环起点，结果插到了目标节点后面，整道题全错。
3.6 一组必须过的测试用例
我建议动手写一个本地main函数，把下面这个流程跑一遍：
- 初始化空链表；
- addAtHead(1)：链表变成1；
- addAtTail(3)：链表变成1->3；
- addAtIndex(1, 2)：链表变成1->2->3；
- get(1)：返回2；
- deleteAtIndex(1)：链表变成1->3；
- get(1)：返回3。
这个例子覆盖了头部插入、尾部插入、中间插入、读取、删除五个核心动作。判题后台会用类似序列来考验你的实现。如果你在自己机器上跑出的结果和手推的不一样，说明某个方法的边界判断或size同步有问题，直接打日志定位。
4. LeetCode 206. 反转链表：迭代和递归两手都要硬
4.1 为什么不能说“把值反过来”
206题要求把链表反转，输入1->2->3->4->5，输出5->4->3->2->1。有些人的第一反应是遍历一遍把值存进数组，再创建新链表。这样确实能过样例，但面试官继续追问“只能遍历一次、空间O(1)”时，你会立刻露馅。因为这题真正想练的是改变指针方向，而不是值交换。链表的核心优势本来就是节点之间的连接方式可以低成本调整，如果靠复制值，等于把链表当成弱化版数组在操作。
4.2 迭代法：让每根指针原地掉头
迭代法只用三个指针：pre、cur、next。它们的职责很清晰：
- pre指向已经反转好部分的头，初始为nullptr；
- cur指向当前要处理的原链表节点，初始为head；
- next保存cur原来的后继，防止反转后找不到后面。
每一步先保存next，再执行cur->next = pre，让当前节点掉头指向前一个节点，然后整体往前挪：pre = cur，cur = next。循环结束后，pre正好停在原链表最后一个节点，也就是新链表的头节点，返回pre。
class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* pre = nullptr; ListNode* cur = head; while (cur != nullptr) { ListNode* next = cur->next; cur->next = pre; pre = cur; cur = next; } return pre; } };有一个地方必须强调：next必须在修改cur->next之前保存。如果先执行cur->next = pre，原链表的后半段就彻底找不到了，这几乎是这道题出现频率最高的错误。我见过很多人在白板上画图很顺畅，但一写代码就把三行顺序搞反。记住一句话：“先存后改，再整体右移”。
4.3 递归法：用“假设子问题已解决”来写
递归写法看代码更短，但理解门槛高一些：
class Solution { public: 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; } };理解递归的关键是不要总想着一层层展开调用栈。你只需要接受一个事实：reverseList(head->next)会把head后面那一整段反转好，并返回反转后的新头。调用结束后，原来的head->next这个节点，变成了反转后链表的尾节点。于是让head->next->next = head，把head接到尾节点后面；再把head->next置空，防止形成环。最后返回newHead。
用具体例子走一下逻辑。输入1->2->3，reverseList(1)先调用reverseList(2)，reverseList(2)又调用reverseList(3)。3的next是nullptr，直接返回自己。回到reverseList(2)，head是2，head->next是3，所以执行3->next = 2，2->next = nullptr，返回3。回到reverseList(1)，head是1，head->next是经过反转后的新链表的尾节点2，于是2->next = 1，1->next = nullptr，最终返回3。整个过程就像把链表的“箭头”逐个反向。
递归的时间复杂度是O(n)，但空间复杂度是O(n)，因为递归最深会压n层栈。在面试里，如果链表长度可能达到几十万，递归方案会面临栈溢出风险。所以面试官通常希望你给出迭代方案，或者至少解释清楚两种方案的取舍。
4.4 另一种思路：头插法构建新链表
除了上面两种，还有一个写法值得掌握：新建一个dummy节点，遍历原链表时把每个节点取下来，用头插法插入dummy之后。它的代码其实和迭代法一个逻辑，只是显式地用了一个新链表头。
class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* dummy = new ListNode(0); while (head != nullptr) { ListNode* next = head->next; head->next = dummy->next; dummy->next = head; head = next; } return dummy->next; } };这段代码里，head每次都被“摘”下来，然后插到dummy后面。和迭代法对比，它把“前驱指针”变成了“新链表头”，更容易理解为什么最终返回dummy->next。这个思路和LeetCode 707里的addAtHead非常像，正好呼应前面两题。
4.5 面试官常追问的几个问题
反转链表看起来简单，面试时却可以延伸出很多问题：
- 如果链表有环，反转会怎样？会形成死循环或错误结构，所以首先要确认无环。
- 如果要求用递归，你会怎么说？要能准确描述递归的终止条件和“子问题假设”。
- 如果要求空间O(1)，只能用迭代。如果要求不修改原链表，就得拷贝节点后反转。
- 如果链表特别长，递归会有栈溢出风险，工程上建议显式用栈或迭代。
这些问题不是背答案就能答好的，前提是真的画图理解指针的变化过程。
5. 训练营第三天常见坑与调试技巧
5.1 链表调试三板斧
链表题出错时，肉眼盯着代码看往往没用，我总结了三板斧。
第一，画图。每道题先在纸上画三到五个节点的链表，把pre、cur、next这些指针标在对应节点旁边，手动走一遍循环。别嫌麻烦，这是最有效的定位方式。很多所谓“灵感”，其实就是画图时看出来的。
第二，打印。准备一个printList函数：
void printList(ListNode* head) { ListNode* cur = head; while (cur != nullptr) { std::cout << cur->val << " -> "; cur = cur->next; } std::cout << "nullptr" << std::endl; }注意循环条件必须是cur != nullptr，不是cur->next != nullptr。前者会打印每个节点包括最后一个，后者会漏掉尾节点，还可能在空链表上访问空指针。
第三，小样例。不要一上来就构造几十个节点的链表，先测空链表、单节点、双节点，再测常规情况。特别是反转链表，单节点和空链表最容易在base case上翻车。
5.2 三个最容易踩的坑
第一个坑是707里的size没维护。插入后忘记加一，删除后忘记减一，get的边界判断立刻失效。这种错误很隐蔽，因为单个方法执行没问题，连续执行后才会出现奇怪结果。解决办法是在每个修改方法里先写size++或size--，再把其他逻辑写完整。
第二个坑是删除节点时指针接错。正确逻辑永远是“前驱的next指向后继”，即cur->next = cur->next->next。新手却经常写成cur = cur->next，这只是移动了遍历指针，链表本身完全没有变化。删除后还要记得释放被删除节点。
第三个坑是反转时丢失后继。206里如果没有先用next保存cur->next，执行cur->next = pre后，原链表后半截就找不回来了。这和707里的头插法顺序错误本质是一回事。遇到这类问题，我建议在纸上把每一步的指针都写出来，而不是在脑子里转。
5.3 必备的临界用例清单
我刷链表题时固定使用下面这批用例，做一次就能覆盖绝大多数边界：
- 空链表：head为nullptr，所有操作都要安全返回，不能崩溃。
- 单节点链表：删除、反转、get都能正确处理。
- 头尾节点删除：验证dummy或前置判断是否有效。
- 连续重复节点：验证删除循环里cur有没有正确“停留”。
- index刚好等于size：707的addAtIndex要能尾插，deleteAtIndex要拒绝。
- index为负数：707规定无效index返回-1或直接忽略，需要判断。
把这组用例整理成自己的“链表测试清单”，每次写完一道题先自己过一遍，再交上去，能省下大量试错时间。
6. 链表专题的通用套路与后续刷题路线
6.1 一套背下来的dummy模板
做了这三题之后，我基本每次碰到链表题都会先问自己三个问题：
- 头节点会不会变化？只要可能变，就用dummy，省去一堆if。
- 需要前驱指针吗？需要就维护pre和cur两个指针，删除、插入基本都离不开。
- 遍历时会不会破坏结构？会就先保存next，再动手改指针。
这三个问题相当于是链表题的“三板斧”。它们不是死记硬背，而是从203、707、206中总结出来的经验：dummy解决头节点变化，pre/cur解决前驱定位，next解决断链保存。面试时遇到没见过的链表题，先把这三个工具列出来，大概率能把解法拼出来。
6.2 下一步可以按什么顺序刷
练完这三题，我建议按下面的顺序继续：
- LeetCode 24 两两交换链表中的节点：考察多个指针同时移动，虚拟头结点非常有用。
- LeetCode 19 删除链表的倒数第N个节点：双指针经典题，先走再一起走。
- LeetCode 160 相交链表：理解链表结构性质，也可以看作“找共同后缀”。
- LeetCode 142 环形链表II：快慢指针加数学分析，能把链表思维再拔高一层。
这些题里，dummy、pre、next三件套依然适用。刷到后面你会发现，自己对链表的感觉已经从“照着题解改”变成“能自己设计”。
6.3 我个人第三天之后的体会
训练营第三天的三题中，让我收获最大的是707设计链表。把五个方法完整写一遍，比连着刷十道简单题都值，因为你会被迫处理addAtHead、addAtTail、addAtIndex之间的细微边界，还会发现“能跑”和“能扛住所有边界”之间隔着很长的距离。我在给模拟项目X写一个简易链表容器时，就把707的代码直接改成了可用的底层结构，过程中又一次确认：边界条件永远比预想的多。链表题没有太多灵光一现，靠的是反复画图、手推、把每种边界都踩一遍。只要把这三题吃透，后面链表题基本都是送分题，这句话等你刷到第19题、第24题时会更有体感。
