1. 为什么第三天就要死磕链表
链表这东西，新手容易觉得简单，老手又容易在细节上翻车。刷题进度到第三天，正好是数组和字符串玩得差不多、开始接触指针操作的节点。这一天安排的三道题——第203题移除链表元素、第707题设计链表、第206题反转链表——看起来是三个独立题目，实际是一条完整的链表基本功训练链。把这三道题吃透，后面再遇到环形链表、相交链表、两两交换节点，都会轻松很多。
先说清楚适合谁看。如果你刚刚学完数组，想搞明白“节点”“指针”“哨兵”这些概念到底在说什么；或者你在刷题平台上做过几道链表题但总是因为边界条件报错；又或者面试前想快速把链表操作捡起来，那么这份记录就是按实际踩坑过程写的。我会把每一道题的思考方式、代码写法、容易错的地方都拆开讲，尽量让没有系统学过数据结构的人也能一步步跟上。
为什么要单独把链表拎出来练？因为数组和链表的思维模式完全不一样。数组是连续内存，靠下标找数据，想删一个元素得把后面所有元素往前搬；链表是零散节点，靠指针串起来，想删一个节点只需要改前后两个节点的指向。这个区别决定了链表题的代码量不大，但指针操作一旦画错，整个链表就拧成一团。我自己见过不少同学，数组题写得很顺，一到链表就栽在“空指针访问”“死循环”“丢链表头”这三件事上。这三道题恰好把这些问题全部覆盖了，值得慢慢磨。
2. 先想通这三道题的关系，再动手写代码
2.1 从数组到链表，思维上要换哪些东西
在数组里，我们习惯用“下标”描述位置，arr[0]、arr[3]，逻辑非常直白。链表里没有下标，只有“当前节点”和“下一个节点”。这样描述位置的方式，从“哪里”变成了“怎么走”。比如要找到第3个节点，得从链表头开始，沿着next指针走两步。这个转换说难不难，说简单也不简单，难在写代码时容易把自己绕晕：到底当前指针是指向第一个节点，还是指向第一个节点的前一个节点？不同写法差一个节点的距离，结果就是边界全错。
还有个更重要的变化：数组的元素是“值”，链表节点是“对象”。我们在数组里交换两个位置，直接换值就行；链表里要调整的是每个节点的next指针。很多人第一次写反转链表时，脑子里想的还是“把值反过来”，结果写完发现链表根本没变。值可以拷贝，但指针关系只能重新连接。这就是为什么链表题通常会要求你画图，不画图纯靠脑子想，很容易在某个节点上迷路。
2.2 三道题的递进关系：操作现有节点、自建完整结构、重新定义连接
如果把这三道题放在同一张训练表上看，逻辑非常清楚。
第203题是“向外输出结果”：给你一条已经存在的链表，让你删掉所有符合条件的目标节点。这题的核心在于遍历链表时，如何用一个当前指针和一个前驱指针协同工作，以及如何处理头节点删除的边界。
第707题是“从零造一个链表类”：你自己定义节点、维护链表长度、实现头部插入、尾部插入、指定位置插入和删除、按下标取值。这题等于把链表的所有基础操作完整做了一遍，做完了，你对虚拟头节点、指针步数、边界长度的理解会扎实非常多。
第206题是“重排既有连接”：不新增节点，也不删除节点，只是把每个节点的next方向从指向后一个变成指向前一个。它训练的是你在原地修改指针结构时，如何保证不丢节点、不回路。
换句话说，第203题教你“在链表上做判断”，第707题教你“把链表的规则定出来”，第206题教你“把链表的连接重新拉一遍”。很多同学刷完这三题后最明显的感受是：链表不再是一堆飘着的箭头，而是一套有迹可循的操作逻辑。这也是这段训练链设计得最妙的地方。
3. 第203题：移除链表元素，先学会怎么“跳过”节点
3.1 题意到底在考什么
题目要求很简单：给定一个链表头节点和一个整数值val，删除链表里所有存储的值等于val的节点。简单来说，就是把这个链表里等于某个值的节点全部摘掉。
最直观的思路是：从头开始遍历，如果遇到一个节点的值等于val，就把前一个节点的next指向这个节点的next。这样当前节点就被“跳过去”了，链表没有它也能完整串起来。这个操作对应到生活里就像整理一串手链：某个珠子不想要了，不是把整串拆了，而是把珠子两边相邻的珠子直接连起来。
但问题马上就来了：如果删除的是第一个节点怎么办？第一个节点没有前一个节点。常见做法是单独判断：如果head的值等于val，就把head指向head->next。这种做法能跑，但每次删除头节点都要写一遍相同的逻辑，而且很容易漏判——新增一个头节点后又需要处理。这个痛点，就引出了链表里非常常用的一个技巧：虚拟头节点。
3.2 用虚拟头节点把特判变成统一逻辑
所谓虚拟头节点，就是自己new一个额外的节点，让它的next指向原来的链表头，然后把这个节点当作遍历的起点。这样原本的“头节点”也有一个统一的前驱节点了，所有删除操作都遵循同一套规则：判断cur->next的值是不是val，如果是，就修改cur->next的指向。整个过程不需要再关心“我删的到底是不是原链表的第一个节点”。
代码长这样：
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; } } head = dummy->next; delete dummy; return head; }我来逐行解释一遍这个写法的思路。dummy就是我们说的虚拟头节点，随便给它一个val，这里用0，反正不会被读到。cur从dummy开始，而不是从head开始。进入循环后，每次盯着cur->next的值：如果它等于val，说明要删掉这个节点。删除前先用tmp把要删的节点存下来，然后把当前节点的next指向要删节点的下一节点，再删除tmp。注意这里删除之后cur不要移动，因为cur->next此时已经是新的节点，它可能还是val，必须继续处理。只有当前节点的下一个节点值不等于val时，cur才往前走一步。最后把dummy的next当作新链表头返回。
这里有一个很多人第一次写会犯的错：在删除节点后，还把cur移动到了cur->next。假如链表中连续两个节点值都是val，你删除第一个后，cur移到了原来第二个节点也就是现在已经变成“新第一个”的位置，然后循环判断'cur->next是否等于val'，实际上你把应该删除的第二个节点漏过去了。所以删除后cur原地不动，这一步是必须记住的。
3.3 什么时候用临时指针，什么时候直接改指向
不少初学者问我：直接就cur->next = cur->next->next，不也能跳过吗？为什么非要先存一个tmp再delete？
两种写法的区别在于是否释放内存。在支持手动管理内存的语言里，如果不删除被摘掉的节点，它就会一直占据内存。刷题时判题系统通常不检查内存泄漏，结果能过，但到了工程上或者在你本地的内存检测工具里，问题就暴露了。另外，如果你不delete，而后面代码里无意中又通过某个旧指针访问那块区域，就会读到已经被重新使用的内存，产生非常难查的bug。我的习惯是：在链表修改类题目里，被摘下来的节点统一用tmp保存后delete，除非题目明确说不用处理。
注意：删除节点之前，必须先保存它的指针，再改变前驱的next。顺序反了，这个节点就找不到了，既没法delete，也等于把一段内存弄丢。
还有个小细节：最后为什么要delete dummy？因为虚拟头节点也是我们自己new出来的，不是原链表的一部分，函数结束后它没用了，不释放就会泄漏。有些刷题平台的判题器不会管这个，但养成好习惯很重要。另外，如果我把head重新赋值成dummy->next，然后再delete dummy，顺序不能反。因为dummy->next就是我们需要的链表头，如果先delete dummy，再取dummy->next就是访问已释放内存，行为未定义。
4. 第707题：设计链表，把链表的操作规则彻底揉碎
4.1 类结构和设计思路
第707题不是给你一条链表去操作，而是让你自己实现一个链表类。题目要求这几个功能：按索引获取节点值，在头部插入，在尾部插入，在指定索引插入，删除指定索引的节点。
这道题做完，你对链表内部结构的理解会有一个质变。我把它当成“试着自己造一个容器”来写，而不是单纯为了过题。
先确定内部状态：一个链表需要知道自己有多少个节点，还需要一个可以统一处理各类插入删除的起点。我选择了两个私有成员：size记录链表元素个数，dummyHead作为虚拟头节点。选择虚拟头节点的理由和第203题一样：让所有插入删除操作都站在“某个节点之后插入/删除”的角度，避免单独处理头节点。
节点结构可以用一个内部结构体：
struct ListNode { int val; ListNode* next; ListNode(int v) : val(v), next(nullptr) {} };类的基本骨架：
class MyLinkedList { private: ListNode* dummyHead; int size; public: MyLinkedList() : size(0) { dummyHead = new ListNode(0); } // 其他方法 };为什么不用尾节点？说实话，加上尾节点可以加速尾部插入，但代价是每种操作都要维护尾节点的正确性，容易出bug。这道题对时间复杂度的要求并不高，先用O(n)的尾部插入把思路写对，等熟练后再考虑优化也不迟。我见过加了尾节点反而把自己绕晕的，因为没有在删除尾节点时正确更新tail指针。
4.2 get方法：从第一个有效节点走index步
get的返回值是第index个节点的值。注意第0个节点就是链表头节点。代码是这样：
int get(int index) { if (index < 0 || index >= size) return -1; ListNode* cur = dummyHead->next; while (index--) { cur = cur->next; } return cur->val; }这里有个细节：cur = dummyHead->next，直接跳到第一个有效节点。因为get要取的是第index个节点，而不是它的前驱。如果从dummyHead开始走index步，走到的是第index个节点的前驱，那取到的值就错位了。很多人在get和其他插入删除方法之间切换时会把起点搞混，我的记忆方式是：凡是“取节点”的操作，从第一个有效节点开始走；凡是“在某个位置前插入/删除”的操作，需要定位到该位置前一个节点，这时候从dummyHead开始走。
4.3 addAtHead和addAtTail：两种最基础的插入
头部插入很简单，把新节点接到dummyHead后面。注意顺序：
void addAtHead(int val) { ListNode* node = new ListNode(val); node->next = dummyHead->next; dummyHead->next = node; size++; }先让node指向原第一个节点，再让dummyHead指向node。顺序一旦反了，先把dummyHead->next改成node，那么原来那个节点就找不到了，因为node的next还没有指向它。
尾部插入需要从头遍历到最后一个节点。最后一个节点的特征是next == nullptr。所以：
void addAtTail(int val) { ListNode* cur = dummyHead; while (cur->next != nullptr) { cur = cur->next; } cur->next = new ListNode(val); size++; }这里cur从dummyHead开始。即使链表为空，dummyHead->next是nullptr，循环直接不执行，cur就是dummyHead，然后给dummyHead->next赋上新节点。完美兼容空链表的情况。
4.4 addAtIndex和deleteAtIndex：边界条件最密集的地方
指定位置插入的规则是：如果index等于链表长度，插在尾部；如果index大于链表长度，不操作；如果index小于0，按头部插入处理。这是题目的原意。我写成直接return非法值或直接忽略。
void addAtIndex(int index, int val) { if (index < 0 || index > size) return; ListNode* cur = dummyHead; while (index--) { cur = cur->next; } ListNode* node = new ListNode(val); node->next = cur->next; cur->next = node; size++; }这里的while (index--)是从dummyHead开始走index步。比如index等于0，循环不执行，cur就是dummyHead，插入位置正好是链表最前面；index等于size，循环走size步，cur停在最后一个节点，插入位置是链表尾部。这个设计相当优雅，也相当容易写错。如果你写的是while (++index)或者while (index > 0) { index--; }，效果不一样，必须自己推一遍。
删除方法更考验边界：
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--; }区别在于index == size的情况：插入可以允许在size的位置，因为插在末尾是合法的；删除如果index == size，那已经越界了，所以条件是index >= size返回。这里犯的错通常是把插入的>和删除的>=搞混，结果在链表为空时莫名访问空指针。
急性子注意：设计链表类时，每个修改操作必须像软件工程里的事务一样同步维护size。增了不增size、删了不删size，后面get和deleteAtIndex的判断全部错乱。这种问题排查起来非常恼火。
4.5 设计链表最容易踩的坑，我一次说全
第一个坑：没有维护size。很多实现从头到尾遍历判断边界，导致get越界时返回错误值，或者插入时明明是第size个位置却走了nullptr。
第二个坑：忘记释放内存。new出来的节点如果只断开引用不delete，长跑程序内存会持续增长。虽然刷题无感，但写本地项目时会被静态检查工具标红。
第三个坑：get和addAtIndex的初始位置搞混。get从dummyHead->next出发，addAtIndex从dummyHead出发。为什么？因为get要找的是目标节点本身，而插入要找的是目标节点的前驱，二者天然差一位。
第四个坑：删除后不把tmp置空或重复delete。delete之后指针变野指针，后续再delete会崩溃。好的习惯是delete后顺手置为nullptr。
第五个坑：没有处理链表为空时deleteAtIndex(0)。如果size为0，边界判断index >= size会直接拦住，所以代码是安全的。但我见过有人把边界条件写成index <= size，就把空链表直接干翻了。
5. 第206题：反转链表，把每个节点的next拧个方向
5.1 迭代法：用两个指针轮流往前走
反转链表是链表题里最经典的题目，没有之一。题目要求把一条链表完全倒过来，比如1->2->3->4变成4->3->2->1。第一眼看上去很吓人，因为我要改变每一个节点的next方向，又不能丢掉还没遍历到的节点。
迭代法的核心思路是：准备两个指针，prev指向已反转部分的前一个节点，cur指向当前要处理的节点。最开始prev是nullptr，cur是head。每一步，先把cur后面的节点用next保存起来，再把cur的next指向prev，也就是把当前这个箭头反拧过来；随后prev和cur各自向前移动一步。
ListNode* reverseList(ListNode* head) { ListNode* prev = nullptr; ListNode* cur = head; while (cur != nullptr) { ListNode* next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; }为什么要先保存next？因为一旦执行cur->next = prev，cur原来的下一个节点就找不到了。链表是单向的，没有保存就会直接断链，后面全部丢失。这三行顺序是固定的：保存next、改指向、移动prev和cur。绝不能改成先移动cur再改指向，那样prev和cur的关系就乱套了。
循环结束后cur变成nullptr，此时prev恰好指向原链表最后一个节点，也就是反转后新的头节点，所以返回值是prev。一个很常见的思想实验是：只用一个指针循环能不能反转？不能，因为单链表节点的next被修改后，你无法回到原来的后继。一定要有两个指针加上一个临时保存，总共三个变量轮转。
5.2 递归法：先假设后面已经处理好
递归版的理解方式和迭代版完全不同，但代码更短。核心思想是：反转一个链表，可以看成把第一个节点接到“反转后的剩余部分”末尾。
递归的终止条件是：链表为空或者只有一个节点，那么它已经反转好了，直接返回。
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。调用reverseList(1)，由于1->next不是空，进入递归调用reverseList(2)。同理进入reverseList(3)。在reverseList(3)里，3->next是nullptr，返回3。回到reverseList(2)这一层，newHead是3。此时执行head->next->next = head，head是2，head->next是3，所以让3的next指向2，然后让2的next指向nullptr，返回newHead=3。回到最外层，head是1，head->next->next就是2->next，指向1，再把1->next指向nullptr。整个链表变成了3->2->1。
这个过程中最关键的是理解递归函数返回的是“反转后的新头”，而不是“当前层原来的头”。很多初学者拿到递归头节点，以为返回head即可，结果链表乱掉。实际上最外层递归拿到的新头是原来的尾节点，只有它才是反转后的头节点。
5.3 反转链表易错点清单
容易错的地方主要集中在两点：一是忘记处理递归中的环，二是迭代中移动指针顺序有问题。
在迭代里，cur->next = prev执行后，如果不把cur移动到next，而是直接把prev赋成cur，就会死循环。我见过的典型错误是这样：
while (cur != nullptr) { ListNode* next = cur->next; prev = cur; cur->next = prev; // 这样写完全错了，cur->next被指回自己？ ... }这种顺序错位会导致节点指向自己，在打印时表现为无限循环。所以在测试反转题时，我习惯在循环里加一个计数器或打印，防止死循环把终端刷爆。
在递归里，容易漏的是head->next = nullptr。如果不把这句写上，原来的头节点还指向第二个节点，会构成一个环。特别是原链表只有两个节点时，1->2会被反转成2->1，但如果最后不把1->next断开，1又指向2，形成了1<->2的环。我之前调试这个bug花了差不多半小时，最后用打印函数发现最后一个节点打印完之后又跳回前面的节点。
6. 链表调试三板斧：打印函数、边界用例、内存习惯
6.1 写一个通用的打印函数
链表的调试没法像数组那样直接打印全部，所以我的习惯是刷题前先备一个打印函数。它不需要多复杂，能把整条链表从头到尾输出成“1->2->3”这样的形式就够了。代码非常简单：
void printList(ListNode* head) { ListNode* cur = head; while (cur != nullptr) { std::cout << cur->val; if (cur->next != nullptr) std::cout << "->"; cur = cur->next; } std::cout << std::endl; }用这个函数配合测试用例，可以在关键步骤后输出链表状态。比如反转链表的方法里，每次处理完一个节点后打印一遍，指针变化就看得清清楚楚。如果没有这个函数，遇到死循环只能盲猜，效率低很多。
6.2 三道题通用的边界用例集合
链表题的边界情况其实非常固定，练多了能形成条件反射。我整理了一份使用频率特别高的用例清单：
| 场景 | 测试用例 | 作用 |
|---|---|---|
| 空链表 | removeElements(null, val) | 确保方法不崩溃 |
| 单节点 | 1，删除值1或删除其他值 | 检查头节点更新 |
| 删除头节点 | 1->2，删除1 | 检查虚拟头节点是否生效 |
| 删除尾节点 | 1->2，删除2 | 检查cur->next为空时处理 |
| 连续重复值 | 1->2->2->3，删除2 | 检查删除后cur是否停留原地 |
| addAtIndex边界 | 在index=0和index=size插入 | 检查前驱定位 |
| deleteAtIndex越界 | index为负数或等于size | 检查合法性判断 |
| 反转的环 | 用两个节点反转，检查旧头next是否断开 | 检查递归结尾置空 |
每次写完链表题，把这份清单过一遍，基本能消灭80%的隐藏bug。我在本地刷题时经常会为这些用例写几行简单的断言函数，比如判断反转后第一个元素是不是原链表的最后一个元素，一旦输出不符合预期，就能快速定位。
6.3 关于内存释放，我最后唠叨两句
很多刷题平台用的是C++的判题环境，但并不会对每个用例做内存泄漏检测，所以即使你new了一堆节点不delete，提交也能通过。我见过有人因此完全不写delete，次数多了就养成了坏习惯。等你到了需要写长生命周期服务的项目里，这种习惯会让内存占用一路飙升。
最好的做法是从刷题第一天就严格要求：每条链上你new出来的节点，要么由链表类在析构函数里统一清理，要么在删除操作中立即delete。比如设计链表这类题，最好补一个析构函数：
~MyLinkedList() { ListNode* cur = dummyHead; while (cur != nullptr) { ListNode* next = cur->next; delete cur; cur = next; } }千万别小看这个析构函数，它能帮你验证自己的代码没有产生环或者悬垂指针。如果链表里出现了环，释放操作会死循环，在本地一跑就暴露了。这也是一个非常有效的检查方法。
7. 我刷完这三题之后最想说的体会
其实最开始刷链表，我也觉得虚拟头节点是个没必要的东西，宁可多写几个if分支。后来被第203题的连续重复节点搞崩过一次，才老老实实用虚拟头。第707题让我彻底理解了为什么所有标准库的容器都要花费那么多精力去维护“结构不变式”——那个size变量就是一个例子。第206题则是对递归的一次很好的脱敏训练，想明白之后，很多树的递归题目也变得顺了。
如果你今天刚开始练这三道题，我的建议是：别急着追求一次bug-free，先把每个方法的执行过程在纸上画一遍，特别是第707题那种多方法类，画一次胜过读十遍代码。画的时候重点标出每次操作后链表的头在哪里、size是多少。等画明白了，再回到编辑器里写代码，你会发现手速突然快了很多。
这三道题不一定非要在同一天刷完，但最好连续刷。因为它们之间是一环扣一环的：虚拟头节点在203里用了一次，在707里又用了一次；双指针思想在203里初见端倪，在206里成为核心；对边界条件的敏感度，则从203一直贯穿到707。真正把这一套打下来，你再看各种链表面试题，脑子里会自动浮现出每一步指针的移动图景——那个状态，才是刷链表题应该有的感觉。
1873号标准地图做QGIS配准与叠加避坑指南)
