企业官网建设流程全解析

直接说结论：链表这块内容，是所有算法训练营里“第一次劝退”的高发区。前两天还在玩数组，下标一打一个准，脑子不用转弯；到了链表，指针指来指去，边界条件一多就晕。但你别怕，链表的题其实很有套路，尤其“代码随想录”这套训练营的第三天三道题——203.移除链表元素、707.设计链表、206.反转链表——正好把链表最核心的操作全串起来了：增删改查、虚拟头节点、指针反转。这三道题吃透，后面二叉树、图论里所有“节点操作”类的题，你都算打了底子。

我先把话撂这儿：这三道题的核心就三件事。

第一件事，虚拟头节点。不用虚拟头，你写移除元素、设计链表，会遇到一个非常烦人的问题：头节点没有前驱，你得单独判断。用了虚拟头，所有节点一视同仁，代码统一，边界问题直接消失一大半。

第二件事，指针操作顺序。链表题翻车，八成是改指针的顺序错了。你先断了人家的next，再想用这个next去找后面的节点，那肯定找不到了。所以“先保存、再断开、后连接”是铁律。

第三件事，反转的本质是改next方向。206反转链表不是“把链表倒过来”，而是“把每个节点的next指向前一个节点”。想通这一点，迭代和递归两种写法你都能写出来。

这篇文章我按训练营的节奏，把三道题从头到尾拆开讲，原理、代码、为什么这么写、坑在哪，全给你盘明白。每道题我都会给可跑的完整代码，语言用C++（训练营主流语言），但思路是通用的，你换成Java、Python、Go都一样的逻辑。最后附上我自己的刷题心得和调试技巧，都是不写在题解里的实战经验。

1. 三道题之间到底什么关系

很多人刷题是一道一道孤立地刷，刷完就忘。这是最大的浪费。其实这三道题是强关联的，我画个逻辑线你就明白了。

1.1 知识点的递进关系

203.移除链表元素，是链表操作里的“删”。它教会你两件事：怎么遍历链表、怎么安全地删除一个节点。而删除一个节点，恰恰需要你掌握前驱节点的概念，这就引出了虚拟头节点。

707.设计链表，是“增删改查”全家桶。它要求你实现一个完整的链表类，包括get、addAtHead、addAtTail、addAtIndex、deleteAtIndex五个方法。这其实就是把203里学的“删”，加上“增”和“查”，整合成一个整体。做这道题，你会彻底搞清楚size怎么维护、index怎么校验、每个操作的复杂度是多少。

206.反转链表，是“改结构”的巅峰。它不增不减，不改值，只把所有next指针的方向调转180度。这在思路上是一个巨大的跳跃，也是后面做回文链表、反转链表II、K个一组翻转链表这些进阶题的基础。

所以你看，这三道题是一条线：从单点操作（删），到完整系统（设计），再到整体结构变换（反转）。难度是螺旋上升的，正好符合训练营“第三天”这个位置——前两天的数组和哈希表是线性思维，链表开始引入“指针”和“引用”这种间接概念，是计算机思维的一个重要转折点。

1.2 它们的共同基石：虚拟头节点

我为什么一直强调虚拟头节点？因为三道题里，有两道直接受益于它。

先说203。删除节点需要让“被删节点的前驱”的next指向“被删节点的后继”。但是链表的头节点没有前驱。你可以单独写一段if判断头节点要不要删、怎么删，可一旦头节点连续好几个都是要删的值呢？那你得用while循环来删，代码开始乱套。用虚拟头节点，虚拟头->next指向真正的头，统一用同一个逻辑遍历删除，写完代码干净利落。

再说707。设计链表的addAtHead，本质就是在“index=0”的位置插入，其他所有index位置的插入逻辑都一样：找到前驱，新节点->next = 前驱->next；前驱->next = 新节点。有了虚拟头节点，addAtHead就不再是特例，它就是普通的addAtIndex(0, val)。这个统一性，能让你的代码少写一半的if-else。

所以我建议你，无论做题时题目有没有要求，凡是设计到“头节点可能被操作”的链表题，第一行就建一个虚拟头节点。这是一个意识层面的升级，比多刷十道题都管用。

2. 203.移除链表元素：先学会“安全删除”

题目要求很简单：给定一个链表的头节点和一个整数val，删除链表中所有满足Node.val == val的节点，返回新的头节点。但“简单”只是看起来简单，里面全是细节。

2.1 为什么不用虚拟头会这么难受

我们先看不用虚拟头的写法。你脑子里第一反应可能是这样：遍历链表，如果当前节点的值等于val，就让前驱的next跳过它。但问题马上就来了：

• 头节点没有前驱，单独判断“头节点要不要删”。但万一头节点删完，新头节点还是val呢？那还得继续判断，所以这里要用while，不是if。
• 如果删除的是中间节点，你要保证当前遍历指针是“前驱的next”，否则你删着删着自己都不知道指到哪去了。

我当时第一次写的时候，代码大概是这个鬼样子：

ListNode* removeElements(ListNode* head, int val) { while (head != NULL && head->val == val) { head = head->next; } ListNode* cur = head; while (cur != NULL && cur->next != NULL) { if (cur->next->val == val) { cur->next = cur->next->next; } else { cur = cur->next; } } return head; }

你看，逻辑勉强对，但有两个不爽的地方。第一，头节点单独处理了，和后续节点处理逻辑不统一，读代码的人得多想一层“为什么要两个循环”。第二，如果链表中所有节点都是要删的，最后head变成NULL，没关系，但你在while里已经把头节点移走了，等于改变了原始链表的引用，这可能会影响外部对头节点的持有（虽然本题返回新头节点没关系，但写工程代码时这是个隐患）。

2.2 用虚拟头节点后，代码长什么样

用虚拟头节点，思路就变成：虚拟头节点dummyHead永远在链表最前面，它的next指向真正的头节点。你从dummyHead开始遍历，每次检查cur->next的值是不是val，是就跳过，不是就前进。

ListNode* removeElements(ListNode* head, int val) { ListNode* dummyHead = new ListNode(0); dummyHead->next = head; ListNode* cur = dummyHead; while (cur->next != NULL) { if (cur->next->val == val) { ListNode* tmp = cur->next; cur->next = cur->next->next; delete tmp; // 如果是在线OJ，这步可有可无；本地测试建议delete防内存泄漏 } else { cur = cur->next; } } head = dummyHead->next; delete dummyHead; return head; }

你看，一个循环搞定所有情况。头节点要删？没问题，cur此时指向dummyHead，cur->next就是原头节点，照删不误。连续的头节点都要删？更没问题，删完一个，cur没动，继续检查新的cur->next，直到不相等为止。

关键点在于：cur始终停留在待删节点的前驱上。只有cur->next的值不等于val时，cur才往前移动。这个设计保证了删除操作永远有前驱可用，也保证了不会漏删连续重复的节点。

注意：delete dummyHead这里有个小讲究。如果你最后delete了dummyHead，那么你不能直接返回dummyHead->next，因为dummyHead已经释放了，虽然返回值是拷贝的指针，逻辑上没问题，但最好先把返回值存下来再释放。上面的代码就先把head更新了再delete，这个顺序别搞反。

2.3 面试时你会被追问的扩展点

这道题虽然简单，但面试官最喜欢加追问。我列几个高频问题，你提前准备：

1. 能不能用递归写？能。递归的终止条件是head为空；递归体是head->next = removeElements(head->next, val)，然后判断head->val是否等于val，等于就返回head->next，否则返回head。但递归有栈溢出风险，工程上还是迭代为主。
2. 为什么tmp = cur->next能防止内存泄漏？因为cur->next = cur->next->next之后，原节点cur->next已经没有任何指针指向它了，在C++里如果不提前用tmp保存它，你就永远丢失了它的地址，没法delete。这就是“先保存、再断开”原则的由来。
3. 如果链表很长，递归会不会爆栈？理论上会，实际刷题时链表长度不会太大，但日常开发中递归处理链表要谨慎。

3. 707.设计链表：把增删改查一次做全

这道题是三道题里最“工程化”的一道。它不考你某个奇技淫巧，而是考你能不能把链表的基本操作完整、准确、边界不出错地实现出来。这道题做得好，说明你的代码组织能力和细节控制能力过关了。

3.1 先设计数据结构：单链表还是双链表

题目一般要求实现单链表即可，但你也可以选择双向链表。单链表简单，内存占用小；双链表找前驱更快，但每个节点多一个prev指针，代码复杂度高。我的建议是：先把单链表做出来，能AC再说。

单链表的节点定义：

struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(NULL) {} };

类定义：

class MyLinkedList { public: 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) { ListNode* newNode = new ListNode(val); newNode->next = dummyHead->next; dummyHead->next = newNode; size++; } void addAtTail(int val) { ListNode* cur = dummyHead; while (cur->next != NULL) { cur = cur->next; } ListNode* newNode = new ListNode(val); cur->next = newNode; size++; } 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; };

3.2 每个方法的边界条件，逐条过

这道题最容易出错的地方就是index的校验。我用一张表把规则整理清楚，你对着看：

这里有个很多人会忽略的细节：addAtIndex是允许index == size的，因为它的含义是在第index个节点之前插入，如果index等于size，说明要插入到末尾之后，也就是尾插。而deleteAtIndex不允许index == size，因为第size个节点根本不存在。

还有一个细节：addAtIndex里，如果index < 0，我习惯set index = 0，而不是return。为啥？因为负index一般理解为“在头部之前插入”，虽然题目没明说，但LeetCode原题里对负index的处理方式是插到头部，兼容性更好。

提醒：size的维护必须和每个操作严格同步。漏掉一次size++或者size--，会导致get越界判断全乱。我见过太多人栽在size上，不是没++就是没--，一跑就线段错误或者越界返回错误值。

3.3 为什么addAtTail这么“笨”也能过

你看上面的addAtTail实现，是从dummyHead开始一步步走到末尾，时间复杂度O(n)。很多人会问：为什么不在类里维护一个tail指针，这样尾插就是O(1)了？

这是个好问题，但你要权衡：一旦加了tail指针，那么删除操作会变得复杂——如果你删的是尾节点，你必须更新tail；更麻烦的是，单链表删除尾节点需要找到它的前驱，这本来就是O(n)，所以就算有tail指针，删除尾节点还是O(n)。与其额外维护一个tail指针增加出错概率，不如老老实实遍历。等以后做双链表或者LRU缓存的时候再引入tail指针不迟。

训练营的写法就是这样：先把最简单的单链表做对，不追求花哨。工程里也是这个道理，先保证正确性，再谈优化。

3.4 内存管理：这道题特别值得注意的点

707题在LeetCode上是允许你new节点不用delete的，因为评测环境会回收进程内存。但如果你在本地用Valgrind检查，会发现内存泄漏。我个人建议，在本地的测试代码里，养成手动delete的习惯，至少养成这个意识。

删除节点时，记得先保存再删除：

ListNode* tmp = cur->next; cur->next = cur->next->next; delete tmp;

千万别写成：

delete cur->next; cur->next = cur->next->next; // 已经访问了被释放的内存，未定义行为！

这段顺序错误轻则崩溃，重则产生难以调试的偶发问题。指向已释放内存的指针就是传说中的“悬垂指针”。另一种常见的写法是先记录要删除的节点，再断开：

ListNode* tmp = cur->next; tmp->next = NULL; // 防止delete时递归释放后续节点（自定义析构时） cur->next = tmp->next; delete tmp;

这种更严谨，在结构体带析构函数时会避免递归释放，不过刷题场景通常不需要这么讲究，但你心里要有数。

4. 206.反转链表：迭代和递归两种写法全攻克

反转链表是链表题里的“hello world”，但也是“面试高频王”。跟移除元素不一样，这道题要求你彻底改变指针的方向。难度不在于代码长，而在于你的脑子里能不能“看到”三个指针在链表上滑动的过程。

4.1 迭代法：三指针滚动

最直观的迭代法，维护三个指针：prev、cur、next。核心逻辑是每次把cur->next指向prev，然后三个指针整体右移。

ListNode* reverseList(ListNode* head) { ListNode* prev = NULL; ListNode* cur = head; while (cur != NULL) { ListNode* next = cur->next; // 先保存后继 cur->next = prev; // 反转指针 prev = cur; // prev右移 cur = next; // cur右移 } return prev; }

你注意，循环结束的条件是cur == NULL，此时prev指向原来的尾节点，也就是反转后的头节点。很多人会写错成while (cur->next != NULL)，这样最后一个节点没处理，返回的也不是完整链表。

这个代码为什么必须先保存next？你试想一下：如果不先保存，你执行cur->next = prev，直接把当前节点的next覆盖成了前驱，那原来的后继节点就再也找不到了，后面的节点全丢。所以next保存的是“后悔药”，保证你能继续往前走。

画个图帮助理解：假设链表是1->2->3->NULL。初始prev=NULL，cur=1。

• 第一步：next=2，1->next=NULL，prev=1，cur=2。此时链表变成1->NULL和2->3->NULL，1和2之间的连接已断。
• 第二步：next=3，2->next=1，prev=2，cur=3。此时链表变成2->1->NULL和3->NULL。
• 第三步：next=NULL，3->next=2，prev=3，cur=NULL。
• 结束，返回prev=3，链表变成3->2->1->NULL。

你发现没，每一步都在“拆掉”一个连接，“建起”一个新连接，旧的连接只用于方便的遍历。这就是“先保存、再断开、后连接”原则的完整呈现。

4.2 进阶难点：反转部分链表（扩展思考）

反转完整链表会做了，面试官一定进阶：反转从m到n的节点。那种题就是在迭代的基础上，记录m位置的前驱和n位置的后继，然后只反转中间的一段。你会发现，m位置前驱的处理，和虚拟头节点的思路是一脉相承的——为了统一边界，你仍然用虚拟头节点，让m=1时不特殊。所以我才说虚拟头节点是个贯穿链表题的大杀器。

4.3 递归法：理解递归的“信任跳跃”

递归版本看起来简洁，但理解起来反而要跳一步。很多人写在递归里总觉得“后面的链表还没反转完，我怎么能先改前面呢”？这里要建立“信任跳跃”：

ListNode* reverseList(ListNode* head) { if (head == NULL || head->next == NULL) return head; ListNode* newHead = reverseList(head->next); head->next->next = head; head->next = NULL; return newHead; }

怎么理解？递归函数reverseList(head->next)的返回值，是“以head->next为头节点的链表，反转后的新头节点”。你假设它已经把这部分反转好了。然后你只需要做两步：

1. head->next->next = head：让原后继节点的next指回head。
2. head->next = NULL：让head的next断开，防止环。

为什么这两步就够了？因为原链表中head->next是唯一指向head的后继的，你让后继指回head，就把head接在了反转后的链表末尾。至于更后面的节点，在递归返回时已经被处理好了。

我一开始学递归，总是想“展开递归栈一层层看”，结果越看越晕。后来我明白了一个道理：递归是让计算机替你做遍历，你只需要关心当前层和自己下面那一层的关系。你不会写循环版的“整个链表反转”，递归就更不敢写。所以我的建议是：先用迭代法把逻辑吃透，再回头看递归，那个“信任跳跃”会容易很多。

提示：递归反转链表有个缺点——如果链表长度达到上万，递归深度过大会导致栈溢出。生产环境里，链表节点数超过几千就建议改用迭代。刷题不用管这个，但面试时可以提一句“我知道递归有栈溢出风险，所以工程上倾向迭代”，这是加分项。

4.4 一个更“野”的思路：头插法反转

如果你理解了虚拟头节点，其实反转链表还有一种写法：遍历原链表，每拿到一个节点，就把它插到dummyHead的后面。这就是“头插法”思维。

ListNode* reverseList(ListNode* head) { ListNode* dummyHead = new ListNode(0); ListNode* cur = head; while (cur != NULL) { ListNode* next = cur->next; cur->next = dummyHead->next; dummyHead->next = cur; cur = next; } return dummyHead->next; }

这个做法的正确性同样依赖于“先保存next”。不过思路完全变了：不是在原链表上改方向，而是“新建一个链表，不断用头插”。我个人觉得，这个方法把反转问题转化成了“构造新链表”，在你脑子转不过来的时候，是一种不错的backup方案。面试时如果迭代法和递归法你都说了，再加上一句“我还能用头插法实现”，面试官对你的印象分会高很多。

5. 实操中常见的坑与排查技巧

这三道题我在训练营里给人答疑的时候，见到的高频错误几乎是固定的几个。我把它们整理成一个速查表，你写完代码后对着自查一遍。

5.1 边界条件错误速查表

5.2 不会调试链表？用“打印大法”

我见过太多人链表题出错，调试手段就是肉眼瞪代码，一瞪瞪半小时。别这样。链表题最适合用打印大法：写一个简单的printList函数，每一步操作后打印一下当前链表状态。

void printList(ListNode* head) { ListNode* cur = head; while (cur != NULL) { cout << cur->val << " -> "; cur = cur->next; } cout << "NULL" << endl; }

像反转链表这种题，你可以在循环的每一步后面都加一行printList(prev)，看到链表一步步被“拆开再拼接”，比想象中容易理解一百倍。你很快就明白为什么“先保存next”是必须的。

5.3 关于本地调试环境的一个建议

很多新人刷题只在线上的编辑框里敲，错了就“肉眼debug”。我的建议是本地装一个C++环境（Visual Studio或者VS Code + 编译器都行），把代码拷下来，自己写main函数，构造测试用例，单步调试或打印调试。链表题尤其适合本地调试，因为你可以亲眼看到每一个节点的地址、val、next值。

举个例子，你想测试“连续头节点都等于val”的边界情况。构造一个链表1->1->1->2->NULL，调用removeElements(head, 1)，看返回的链表对不对。这种用例在LeetCode上也能跑，但本地跑你可以打断点，观察每一步cur指针的指向，这对形成“指针感”非常重要。

我在训练营里看到过很多转码的同学，一开始最欠缺的不是知识，而是调试的自信。他们不敢print、不敢打断点，就干瞪眼。我特别想说：代码是写出来的，也是调出来的。调一次链表的bug，比刷三道链表题都长经验。

6. 三道题做完之后，你还应该做点什么

训练营第三天做完，别急着往后冲。花二十分钟做一次“复盘”，比盲目刷新题强。

6.1 一个复盘清单

1. 不看任何笔记，把206反转链表默写出来。迭代法和递归法各写一遍。默写不出来，说明还没内化，回去再看。
2. 把707设计链表的每个方法的边界条件画成表。你能画出界表，说明你真的理解了size和index的关系。
3. 把203的递归写法也写出来。能写出递归，说明你对“后续节点递归处理完”的信任跳跃有了感觉。
4. 思考一个问题：如果链表中存在环，反转链表会怎样？会死循环。那如何检测环？这引出了快慢指针，也就是下一阶段要学的经典技巧。

这个复盘清单，其实就是在刻意训练你“从多角度理解同一个问题”的能力。因为算法面试考的不是你背了多少题，而是你能不能灵活迁移。

6.2 后续刷题路线建议

链表这部分，至少建议按这个顺序继续：23. 合并K个升序链表 -> 24. 两两交换链表中的节点 -> 25. K个一组翻转链表 -> 143. 重排链表 -> 234. 回文链表 -> 141. 环形链表（快慢指针入门）。

你会发现，这些题全都建立在今天这三道题的基础上。尤其是K个一组翻转链表，它就是反转链表的复杂版：先算出长度，分段反转，每段反转用的还是206的迭代法，只不过每段开始前要记住prev和next。你如果206真的吃透了，K个一组翻转链表就是一个“多写几行”的问题，难度不大。

6.3 关于训练营学习方法的一点个人体会

跟训练营刷题，最重要的是别“眼睛会了手不会”。方法再对，你不自己敲一遍，永远不知道哪一行会卡住。我今天讲得再细，都不如你自己在编辑器里按着报错一个一个改。我甚至可以这么说：如果你写完这三道题，一次都没报过错，那你的收获比报过错的人少一半。因为报错的那个瞬间，才是你大脑真正开始建立神经连接的时刻。

我当年刷链表的时候，最崩溃的一次是把707的deleteAtIndex写错，本地一跑直接段错误。我当时完全没有头绪，最后是单步调试一步步看，才发现删除最后一个节点后size没有减，下次get的时候越界了。那一刻之后，我再也没忘记“所有变更size的操作必须同步更新”。这种“痛过才记住”的经验，比任何人告诉你都牢靠。

所以，别怕错，多调试，把每一个报错当作一次学习机会。链表三道题做完，你会明显感觉看代码的能力上了一个台阶——从“看一行代码理解一行”变成“看到cur->next = cur->next->next，直接脑补出链表的那根线断掉又接上”。这种感觉一旦出现，你就真的入门了。

最后再分享一个小技巧：以后你做任何链表题，先画图再做。拿一张纸，把节点画成方框，把next画成箭头，然后模拟一遍整个过程。画三步，胜过你在脑子里空转十分钟。这个习惯，我到现在写工程代码设计链表结构的时候还在用。