链表刷题第三天：虚拟头节点与双指针反转的实战思路

算法训练营第三天，任务列表里写着链表理论基础、203 移除链表元素、707 设计链表、206 反转链表。说实话，第一天学数组、第二天刷双指针，脑子里画的都是连续格子，今天突然要切换到链表的指针世界，确实有种被拽着转弯的感觉。把这三道题完整做下来之后，我发现一个特别朴素但重要的结论：链表题如果不动手画图，光靠盯着代码空想，很容易在一个next赋值上卡半小时；反过来，画清楚每一步指针的指向，代码其实也就几行的事。这篇文章就把我第三天的完整思路、踩坑和调试习惯记录下来，给同样在刷链表的朋友一点参考。

1. 链表理论基础：训练营第三天要先补的认知

1.1 链表和数组的本质差异：内存布局决定操作习惯

很多人在数组题里养成的习惯是"下标即位置"，到了链表还下意识想用cur[i]去访问元素，这是第三天最先要纠正的地方。

数组在内存里是一段连续空间，每个元素紧挨着放，所以通过首地址加偏移量就能直接算出目标位置，随机访问的时间复杂度是 O(1)。但也正因为连续，在数组中间插入或删除一个元素，往往要把后面的元素整体搬移，最坏情况是 O(n)。

链表不一样，每个节点在内存里是分散的，节点之间靠一个next指针"手拉手"串起来。想找到某个节点，只能从头节点出发，顺着指针一个一个走，所以随机访问是 O(n)。但如果在已知前置节点的前提下做插入或删除，只需要改动几个指针，操作本身是 O(1) 的。这也是为什么链表更适合"频繁增删、较少按下标访问"的场景。

第三天做题时我会反复提醒自己：链表题所有的时间复杂度分析，都要围绕"遍历了几个节点"来算，而不是"执行了几行代码"。

1.2 单链表定义方式与几个关键约定

刷链表题第一步不是写算法，而是先确认链表节点的定义。LeetCode 的 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) {} };

在本地写代码时也要先把这三行构造函数的版本准备好，尤其要养成"构造完节点立刻置next为空"的习惯。很多 bug 都来自新建节点后忘记初始化指针，导致后面遍历时访问到野指针。

对于链表题，我习惯做两个约定：第一，头节点用head表示；第二，用一个cur指针做遍历游标，不直接修改head本身，除非题目明确要求返回新的头节点。这个习惯能避免很多"把头节点弄丢了"的问题，后面设计链表和反转链表时特别明显。

1.3 虚拟头节点：让增删逻辑不再分叉

链表题里最烦的一种情况就是"操作的是头节点"和"操作的不是头节点"需要分开写。比如删除节点，如果先删头节点，那head本身要往后移；如果删的是中间节点，又需要借助前置节点的next去跳过目标节点。两种情况代码不一样，判断条件一多就容易漏。

虚拟头节点（dummyHead）就是用来解决这个问题的。它本身不存有效数据，只是挂在真正的头节点前面，让头节点在代码里的角色跟普通节点完全一致。这样一来，所有增删操作都能从dummyHead出发，用同一套遍历逻辑处理，不需要对头节点做额外分支。

这个知识点看似简单，但第三天的三道题全都在用同一个思路：203 用一个虚拟头节点收拢删除逻辑，707 直接用虚拟头节点作为类的内部结构，206 反转链表时pre指针初始化为nullptr，本质上也是一种"在头部前面补一个空节点"的思想。把这些题放在同一天练，其实就是在反复强化同一个认知。

2. 移除链表元素（203）：从分情况讨论到统一写法

2.1 题目要求与最直观的删除套路

203 的题意很直白：给一个链表和一个目标值val，把链表中所有值等于val的节点全部删掉。比如链表是1 -> 2 -> 6 -> 3 -> 6，目标值是 6，最终要把两个 6 都去掉，返回1 -> 2 -> 3。

先说不加虚拟头节点的朴素写法。删除一个节点需要让它的前驱节点指向它的后继节点，但头节点没有前驱，所以头节点必须单独处理。于是代码自然分成了两段：

// 先处理头节点 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; } }

这段逻辑本身是对的，但它暴露了两个问题：第一，头节点和非头节点用了两套代码，后续改动容易只改一半；第二，如果链表里所有节点都要删，第一段循环执行完后head已经变成nullptr，第二段循环的空指针判断要格外小心。

2.2 用虚拟头节点把删除逻辑收拢成一套

加一个虚拟头节点之后，头节点就不再是"特殊节点"了。万能的遍历逻辑是：让cur从dummyHead出发，每次检查cur->next的值，如果等于val就删掉cur->next，否则cur往后走一步。

ListNode* removeElements(ListNode* head, int val) { ListNode* dummyHead = new ListNode(0); dummyHead->next = head; ListNode* cur = dummyHead; 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 dummyHead->next; }

很多人在写这段代码时会犯一个典型错误：删除节点之后，cur仍然停留在原地，而cur->next可能已经指向了下一个待检查的节点，所以不需要cur = cur->next；只有当前节点不需要删除时，cur才向后挪。这一步是每次删除循环里的关键判断，千万别统一写成"判断完就cur = cur->next"，否则会跳过被删除节点后面紧跟的元素。

返回值也要注意：最终应该返回dummyHead->next，因为原链表的头节点可能已经被删掉了，dummyHead->next才是新的头。如果只返回head，某些边界情况下会返回一个过期指针。这里其实能顺便写出一个通用删除模板：凡是涉及"可能删头节点"的题，都先初始化一个虚拟头节点，最后返回它的next。

2.3 C++ 内存释放：一个容易被忽略的细节

用 C++ 刷题时，删除节点不只是改指针，还要记得释放内存。上面的代码里用delete tmp释放了被删节点，这一步如果漏掉，LeetCode 平台通常不会报错，但会带来内存泄漏；更危险的是某些本地环境里，不释放内存会导致后续节点分配出现奇怪的复现问题。

我写链表题一直以来都有一个习惯：凡是delete掉的指针，紧接着就要让它的使用结束，不要在后续代码里再引用。同时，虚拟头节点是在堆上new出来的，函数末尾最好也delete dummyHead。完整版本可以写成：

ListNode* removeElements(ListNode* head, int val) { ListNode* dummyHead = new ListNode(0); dummyHead->next = head; ListNode* cur = dummyHead; 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* newHead = dummyHead->next; delete dummyHead; return newHead; }

这道题的时间复杂度是 O(n)，空间复杂度是 O(1)，因为只遍历了一次链表，额外只用了一个虚拟头节点。对第三天来说，这个复杂度结论不难，但很多人会忘记"单次遍历"正是链表的操作特征，如果写出两趟循环来删节点，虽然也能过，但不符合这道题想要的练习方向。

3. 设计链表（707）：五道接口题怎么组织内部结构

3.1 内部变量设计：dummyHead 和 size 是核心

707 是一道"把链表常用操作全写一遍"的综合题，要求实现get、addAtHead、addAtTail、addAtIndex、deleteAtIndex五个接口。这道题最妙的地方在于，它逼你把链表操作的所有边界条件都考虑一遍，而不是只写一个孤立函数。

我第一时间确定的内部结构只有两个变量：一个是虚拟头节点指针dummyHead，另一个是整数size。

为什么要记size？因为get(index)和deleteAtIndex(index)都需要先判断索引是否越界。如果不维护size，就得每次遍历整个链表去数节点数，时间复杂度直接恶化；维护了size，判断越界就是 O(1) 的事，增删节点时同步增减即可。

dummyHead在这个类里的作用比在普通题目里更明显：如果没有虚拟头节点，addAtHead会需要特殊处理head本身，而有了它，头插和中间插入完全可以共用同一个addAtIndex的处理思路，代码量少很多，也少很多分支。

3.2 addAtIndex 是整个类的关键枢纽

五个接口里最难写的是addAtIndex(index, val)：在第index个节点之前插入一个新节点。题目有个边界条件很多人第一次写会踩坑：如果index == size，新节点要追加到链表末尾，这是合法的；如果index > size，这步操作什么都不做；如果index < 0，则插入到头部。

这里我的做法是把所有插入操作都收敛到addAtIndex：

void addAtIndex(int index, int val) { if (index > size) return; index = max(0, index); ListNode* newNode = new ListNode(val); ListNode* cur = dummyHead; while (index-- > 0) { cur = cur->next; } newNode->next = cur->next; cur->next = newNode; size++; }

这个实现里的关键点是：cur从dummyHead出发，走index步之后，cur正好是目标位置的前驱节点。比如要在开头插入，index = 0，cur停在dummyHead，新节点直接插到原头节点前面；要在尾部插入，index = size，cur会走出链表末尾，停在最后一个真实节点上，新节点就接到了末尾。

我建议把addAtHead和addAtTail直接复用这个函数：

void addAtHead(int val) { addAtIndex(0, val); } void addAtTail(int val) { addAtIndex(size, val); }

这样写的好处是，后续如果修 bug，只需要改addAtIndex一处，其他方法都会跟着修正。这种"单一入口"的设计在真实工程里也很有价值。

3.3 get、delete 与 addAtTail 的边界条件

get(index)的逻辑是先判断索引越界，再从头节点的下一个节点开始走index步：

int get(int index) { if (index < 0 || index >= size) return -1; ListNode* cur = dummyHead->next; while (index-- > 0) { cur = cur->next; } return cur->val; }

这里要注意，get得到的是第index个有效节点，而插入时走index步得到的是前驱节点，两者的起点不同：一个从dummyHead->next出发，一个从dummyHead出发。如果不能区分这两者的差别，写代码时很容易多走一步或者少走一步。

deleteAtIndex(index)的边界条件更严格：index < 0 || index >= size都直接返回，注意index == size在这里是非法的，因为没有第size个节点可以删。删除时同样从dummyHead出发走index步，找到前驱节点，然后跳过目标节点并释放内存。

还有一个小细节：遍历时我习惯用while (index-- > 0)，这个写法会修改index的值，因为传入参数是值传递，所以没问题；但如果你写的是引用参数，就要小心临时把index存下来。边界情况越多，越要留意这类副作用。

3.4 一个完整的参考实现

把上面的逻辑串起来，我第三天最终采用的完整实现是这样：

class MyLinkedList { private: struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; int size; ListNode* dummyHead; 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-- > 0) cur = cur->next; return cur->val; } void addAtHead(int val) { addAtIndex(0, val); } void addAtTail(int val) { addAtIndex(size, val); } void addAtIndex(int index, int val) { if (index > size) return; index = max(0, index); ListNode* pred = dummyHead; while (index-- > 0) pred = pred->next; ListNode* newNode = new ListNode(val); newNode->next = pred->next; pred->next = newNode; size++; } void deleteAtIndex(int index) { if (index < 0 || index >= size) return; ListNode* pred = dummyHead; while (index-- > 0) pred = pred->next; ListNode* tmp = pred->next; pred->next = pred->next->next; delete tmp; size--; } };

刷这道题时我有个体会：707 表面是五道小题，实际上它把所有链表操作串成了一个闭环。无论addAtIndex怎么复杂，只要把"寻找前驱节点"这个核心步骤想清楚，后面每个方法都能复用同一套思路。第三天把这道题写完后，再回去看 203 的虚拟头节点写法，会觉得异常自然。

4. 反转链表（206）：双指针思路的推导与递归对照

4.1 为什么直接改 next 顺序会翻车

206 的题意很简单：把链表1 -> 2 -> 3 -> 4 -> 5反转成5 -> 4 -> 3 -> 2 -> 1。但真正动手写的时候，很多人第一反应是"把每个节点的 next 指向前一个节点不就完了"。这个方向是对的，但因为链表只能从前往后走，直接把cur->next指向前一个节点之后，原来后面的节点就找不到了。

比如cur指向1的时候，如果把1->next改成nullptr，链表就从2这里断了，后面2、3、4、5全部丢失。这就是为什么反转链表必须有一个临时变量，在覆盖cur->next之前，先把原来的下一个节点保存下来。

这个"先保存、再覆盖、再后移"的动作，正是第三天训练营最强调的指针操作基本功。你可以理解为：链表就像一串手拉手的人，现在要让每个人都改拉前一个人，那你必须先看清自己身后是谁，然后再松手，否则身后的人就散了。

4.2 双指针迭代法：pre、cur、temp 的三角配合

最经典的解法是双指针迭代。维护两个指针pre和cur，初始时pre为nullptr，cur为head。每一轮循环做四件事：

• 用temp保存cur->next，防止丢失后继；
• 让cur->next指向pre，完成当前节点的反转；
• 把pre移到cur；
• 把cur移到temp。

写成代码就是：

ListNode* reverseList(ListNode* head) { ListNode* pre = nullptr; ListNode* cur = head; ListNode* temp; while (cur != nullptr) { temp = cur->next; cur->next = pre; pre = cur; cur = temp; } return pre; }

这四步的顺序一个都不能换。temp的赋值必须在cur->next被覆盖之前，否则原来的链表断了，后面的节点就全丢了；pre = cur和cur = temp的顺序也不能颠倒，先移动cur的话pre就指向了错误的节点。

为了让这个循环更直观，第三天我在纸上画了一张表，按表头列出temp、cur->next、pre、cur四列，拿1 -> 2 -> 3手动走了一遍：

轮次	操作前 cur	temp = cur->next	反转后 cur->next	本轮结束后 pre	本轮结束后 cur
初始	1	-	-	nullptr	1
第 1 轮	1	2	nullptr	1	2
第 2 轮	2	3	1	2	3
第 3 轮	3	nullptr	2	3	nullptr

循环结束后cur为空，pre正好停在原链表最后一个节点上，所以返回pre。很多同学刚学这道题时会想"为什么返回pre而不是head"——因为反转之后原来的头节点变成了尾巴，它的next是nullptr，而pre走到了原来的尾巴上，这才是新链表的头。

4.3 递归法：和双指针几乎一一对应

等到双指针版本写熟了，递归版本就很好懂。递归函数其实就是在用函数栈保存"当前轮次的参数"，逻辑跟双指针完全一致：

ListNode* reverseList(ListNode* head) { return reverse(nullptr, head); } ListNode* reverse(ListNode* pre, ListNode* cur) { if (cur == nullptr) return pre; ListNode* temp = cur->next; cur->next = pre; return reverse(cur, temp); }

这里reverse(pre, cur)对应双指针中的一轮循环，cur == nullptr对应循环结束条件，return pre对应最后返回cur的前一个节点。递归写法在训练营里属于"理解了就行"的进阶内容，面试时如果被要求只能用递归，可以直接照这个模板写。

递归版本还有一种写法是"从后往前递归"，先递归到链表末尾，然后一路往回改next。这种思路也能反转，但新手容易绕进去，而且代码里需要额外把新的头节点一路带回最外层。我的建议是：先练双指针和上面那种"递归模拟双指针"的版本，从后往前的写法等模拟熟练之后再去看，会更容易理解。

5. 三题连做后的高频踩坑点与训练建议

5.1 画图是链表题的 Debug 利器

第三天做完三道题，最想分享的一条经验就是：链表题一定要画图。不是为了仪式感，是因为链表的指针操作在代码里太抽象，人的短期记忆根本扛不住三个以上的指针互相拆指向。

我的画图习惯很朴素：把每个节点画成一个方框，方框里写上值和箭头，箭头指向下一个方框。每跑一行代码，就用橡皮擦掉旧箭头，画上新箭头。这样走完一小段循环，整个逻辑就会非常清楚，哪里多指了、哪里丢了后继，一眼就能看出来。

尤其是 206 反转链表，如果不画图，第一次很容易困惑"为什么temp保存完之后，cur不能直接等于cur->next？"可一旦画了图你就会发现，cur->next早就被改成指向pre了，再取cur->next拿到的根本不是原来的后继节点。这种问题画图后几乎不会再犯。

5.2 三天里最值得记下的几个坑

刷完这三道题，我把最容易出错的几个点集中记了一遍，分享一下：

第一，707 的索引边界容易混乱。addAtIndex的index == size是合法的，因为插入点可以是链表末尾这个位置；但deleteAtIndex的index == size是非法的，因为根本没有第size个节点可以删。很多同学写完addAtIndex之后照抄边界到deleteAtIndex，结果就漏了这个差别。

第二，反转链表里temp的位置不能挪。有些写法会把temp = cur->next放在cur->next = pre之后，这样temp取得的是反转后的旧值，等于没保存，链表直接断了。一定要让"保存下一个节点"成为循环体的第一步。

第三，删除节点时cur不要盲目后移。203 里如果删掉了一个节点，cur->next已经被更新为隔一个节点的新指针，这新指针还没被检查过，所以cur必须停在原地，下一轮继续检查；只有当当前节点不需要删除时，cur才向后移动。这一点对于连续出现多个目标值的情况特别重要。

还有一个小细节是内存管理。C++ 里用new创建的节点，删除时要delete；707 的MyLinkedList析构时最好把链表中所有剩余节点都释放掉，训练营打卡阶段可能不检查内存泄漏，但养成这个习惯对后续做更复杂的题只有好处。

5.3 这天的做题节奏怎么安排比较稳

第三个训练日内容确实不算少，我的节奏建议是按照"先理论、再 203、再 707、最后 206"的顺序走。203 是最容易入门的"删除模板题"，先通过它把虚拟头节点的套路熟悉起来；707 是五个接口的综合运用，把 203 里那个"从虚拟头节点出发找前驱"的方法延伸一下就能写；206 是最需要变换思维的题，放到最后注意力最集中时做反而更容易画明白。

如果你当天时间比较紧，至少要把 203 的虚拟头节点写法完全吃透，再把 206 的双指针法背下来并手动模拟一遍。707 的完整实现可以作为第二天复习时的复练题。不是每道题都必须一次刷到滚瓜烂熟，重点是每天都能有一套自己理解的"通用套路"，链表题其实翻来覆去就是在考：找前驱、存后继、改指向、清内存。

第三天整体走完，最大的感受是链表并没有想象中那么难，难的是把抽象指针变成纸面上的箭头。只要愿意多画几遍图，把每个节点的指向都落实到笔尖，后续再遇到链表的环、相交、排序等问题，至少不会一上来就慌了。