链表刷题核心框架：虚拟头节点与三大经典操作实战

算法训练营进入第三天，今天正式从数组切到链表。昨天还在讲双指针和滑动窗口，今天就变成了指针的指向、节点的增删。今天安排的三道题——203. 移除链表元素、707. 设计链表、206. 反转链表，其实是一条非常丝滑的学习链路：先用最简单的删除题建立链表操作的基本手感，再用“设计链表”把增删查改五个接口一次补齐，最后用反转链表把指针扭转的思维彻底打通。如果你在准备面试、正在系统刷题，或者只是想把链表这块地基补牢，这篇文章可以直接跟着走一遍，三道题全部贴完整代码，附带我实际踩过的坑。

很多初学者一碰到链表题就发怵，不是因为题目难，而是因为脑子里没有一套稳定的解题框架。今天这篇文章的目标就是把框架给你搭起来：虚拟头节点怎么用、指针操作顺序怎么记、边界条件怎么想全。把这三道题吃透之后，再去做两两交换节点、环形链表这类进阶题，你会发现底层逻辑全部是通的。

1. 链表理论基础：先搞清链表的“性格”

1.1 数组与链表的本质区别：连续 vs 离散

要理解链表题，先要理解链表和数组在内存里的根本差异。数组在内存中是一段连续空间，元素一个挨着一个；链表节点则是散落各处的独立对象，通过“指针”串起来。用生活化的例子来讲，数组就像电影院连排座位，你知道自己的位置，随便一坐就能找到左右邻居；链表更像寻宝游戏，手里只有一张线索纸条，上面写着下一个线索藏在哪里，你必须顺着线索一个个找。

这个差异直接决定了两种数据结构的能力边界。数组随机访问是 O(1)，只要知道下标就能直接定位；链表随机访问是 O(n)，想拿到第 k 个节点必须从头遍历。但数组在头部插入或删除元素时需要把后面所有元素整体搬移，是 O(n)；链表插入删除只要改指针，理论是 O(1)。注意这里有个前提，插入或者删除必须已经定位到目标节点的前驱节点，否则仅凭头节点还是要遍历到对应位置，整体还是 O(n)。

还要提一点很多人忽略的缓存局部性。数组在内存里连续存放，CPU 加载一片内存时能把一串元素同时载入缓存，遍历速度极快；链表节点散落，每次访问都可能触发一次内存跳转，缓存命中率低，实际运行速度比数组慢得多。LeetCode 上跑链表题看不出差距，但在高并发、大流量的真实服务里，这个差异会被放大得很明显。所以工程上能用连续内存容器存储的，一般不会优先用链表。

1.2 单链表的基本结构定义与内存模型

链表节点在 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) {} };

一个节点就两个部分：数据域存值，指针域存下一个节点的地址。链表题里频繁出现的构造函数重载，是为了方便写测试代码。比如new ListNode(5)就能创建值为 5 的节点，new ListNode(5, node)则创建一个值为 5、next 指向 node 的新节点，日常调试非常有用。

除了单链表，还有双链表和循环链表。双链表的每个节点多一个prev指针指向前驱，可以双向遍历，代价是多占一份内存。循环链表则是让尾节点的next指向头节点，形成闭环，适合约瑟夫问题这类场景。今天的三道题都以单链表为主，707 设计链表也可以用双链表实现，但训练阶段我更推荐单链表版本，因为单链表能把指针操作最核心的难点暴露出来。

1.3 虚拟头节点的设计哲学

链表题里最容易被绕晕的点，就是“头节点”的特殊性。普通节点的增删改，只需要操作它的前驱节点；但头节点没有前驱，一旦要删除或替换，就得直接修改head指针本身。这样代码里就会出现两套逻辑：处理头节点是一套，处理其他节点是另一套。两套逻辑就意味着多一处出错的可能。

虚拟头节点（dummy head）就是为了消除这种割裂感而存在的。做法很简单：手动创建一个不参与实际数据的节点，让它的next指向真正的头节点，然后永远从虚拟头节点开始操作。这样一来，原来的头节点和其他节点地位完全相同，所有增删操作统一用同一套“找前驱、改指针”的逻辑。

ListNode* dummyHead = new ListNode(0); dummyHead->next = head;

不少初学者觉得虚拟头节点多此一举，直接判断head不就行了？确实可以，但代码会变得更啰嗦，而且容易漏判定。以我刷了几百道链表题的经验来说，凡是涉及删除、插入、反转的链表题，虚拟头节点几乎都是最优解。唯一的注意点是最后返回结果时，别把dummyHead本身返回出去，要返回dummyHead->next。

1.4 链表操作的时间复杂度一览

整理一张常用操作的时间复杂度对照表，方便随时查：

这张表想说明两件事。第一，链表适合频繁在头部或已知位置附近做插入删除的场景；第二，链表并不是万能银弹，尾部插入和随机访问都被数组碾压。理解了这些特性，面试时聊“为什么这里用链表不用数组”才能真正答到点上。

2. 203. 移除链表元素：头节点处理是第一个坎

2.1 题目要求与核心陷阱

题目要求很直白：给一个链表头节点head和一个整数val，删除链表中所有值等于val的节点，返回新的头节点。

因为链表可能从第一个节点就开始删，所以返回值不一定是原来的head。这是第一道坎：很多人习惯性地return head;，结果头节点被删掉时，返回的指针已经指向一块被释放的内存或者一个仍然存在但不该存在的旧节点，程序直接报错或者答案错误。

这道题第二个容易踩的坑是 C++ 的内存释放。C++ 的delete不会自动把指针置空，删除节点后如果不把前驱的next正确接上，就会出现野指针。Java 和 Python 不需要手动释放内存，写起来轻松，但面试时如果追问内存模型，反而容易被问住。

2.2 不带头节点的解法：头节点要单独判断

先看不带虚拟头节点的写法，理解它的痛点：

ListNode* removeElements(ListNode* head, int val) { // 先处理头节点连续等于 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缺一不可。第一个循环解决头节点连续是val的情况，比如链表是1 -> 1 -> 1 -> 2，必须循环删到head不再是val为止。第二个循环从当前head出发，一直检查cur->next的值，命中就删除，否则cur后移。

注意第二个循环里，删除节点时cur不能移动。为什么？因为cur->next被替换成下下个节点后，新顶上来的节点可能还是等于val，如果此时cur后移，这个新节点就漏检查了。这个细节是初学者最容易忽略的。

2.3 带头节点的解法：删除逻辑完全统一

引入虚拟头节点之后，代码可以精简不少：

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; } } head = dummyHead->next; delete dummyHead; return head; }

对比两版代码，会发现带头节点的版本删掉了一整个while循环。原因正如前面所说，虚拟头节点让“删除头节点”和“删除中间节点”的逻辑统一了：永远是站在前驱节点的视角去删除后继。循环条件cur->next != nullptr也天然规避了cur为空导致的空指针。

这里还要提醒一句：C++ 里dummyHead是new出来的，用完记得delete。很多人写完功能忘了释放，测试倒是能过，但面试官一问内存泄漏就露馅了。Java 和 Python 看不上这个细节，但 C++ 选手必须养成好习惯。

2.4 边界条件与经验提醒

这道题的边界条件比较典型，完全可以背下来当模板测试用：

• 空链表：head == nullptr，直接返回head。
• 全删：所有节点值都等于val，最后返回nullptr。
• 连续删除：链表中存在连续多个等于val的节点，要确保全部删除。
• 头节点被删后新头还是val。
• 给定val在链表中不存在：链表原样返回。

我个人刷这道题的体感是，第一遍写不带虚拟头节点的版本能通过，但耗时明显更长，因为大脑要在两套逻辑之间来回切换。第二遍用虚拟头节点就顺多了。所以我的建议是：链表删除类题目，默认直接上虚拟头节点，不要犹豫。

3. 707. 设计链表：把底层操作完整过一遍

3.1 这道题到底想考什么

707 题要求设计一个链表类，实现五个接口：

• get(index)：获取链表中下标为 index 的节点的值
• addAtHead(val)：在链表头部插入
• addAtTail(val)：在链表尾部插入
• addAtIndex(index, val)：在下标为 index 的节点前插入
• deleteAtIndex(index)：删除下标为 index 的节点

很多第一次做这道题的人会低估它，觉得这不就是最基础的链表操作吗？但真正写起来才发现问题很多：下标从 0 开始、index可能非法、addAtIndex中index可以等于链表长度、指针连接的先后顺序不能错、size必须在每个操作后正确维护……可以说，这道题把所有链表基础操作的坑一次性集成到了一个小型类里。

之所以把它放在 203 之后，是因为它需要你从“用别人写好的链表”切换到“自己实现链表”。这个视角转换才是关键：调用者只关心接口语义，实现者必须关注内存、指针、边界。

3.2 基础字段设计与初始化

我建议用单链表 + 虚拟头节点 + 显式维护size的方案：

class MyLinkedList { private: ListNode* dummyHead; int size; public: MyLinkedList() { dummyHead = new ListNode(0); size = 0; } };

size字段一定要维护好，它能省掉很多麻烦：判断index是否非法时直接跟size比，不用遍历链表数节点数量；addAtIndex里index == size表示插入到尾部，这时也能通过size迅速确认这是合法操作。

有人可能会问，为什么用虚拟头节点而不是直接存一个head指针？因为有了dummyHead，五个接口里就不需要针对“头节点为空”或者“插入头部”做特判，所有操作都统一成“找到目标位置的前驱节点，然后操作它的next”。

3.3 五个接口逐个击破

第一个接口get：

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

cur指向第一个有效节点，while (index--)循环走 index 步，最终停留在下标为 index 的节点。注意这里不能用cur->next去判断循环结束，因为index >= size已经在前面被拦截了，剩下的就是简单的“走几步”问题。

第二个接口addAtHead：

void addAtHead(int val) { ListNode* node = new ListNode(val); node->next = dummyHead->next; dummyHead->next = node; ++size; }

核心顺序是先把新节点的next指向旧头节点，再让虚拟头节点指向新节点。顺序反了的话，新节点就指向了自己或者丢失了后续链表，这是常见的指针误操作。

第三个接口addAtTail：

void addAtTail(int val) { ListNode* cur = dummyHead; while (cur->next != nullptr) { cur = cur->next; } cur->next = new ListNode(val); ++size; }

尾部插入只能遍历到最后一个节点，然后把它的next指向新节点。这里我习惯用while (cur->next != nullptr)而不是while (cur != nullptr)，因为我们要停在尾节点而不是走到空节点，停错了就加不上了。

第四个接口addAtIndex，我认为是整个类里最容易写错的一个：

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

题目要求index小于 0 时插在头部，index大于链表长度时直接不插入。这里很多人会写成index >= size就返回，但如果index == size，其实是合法的尾部插入。一定要分清>和>=。

先走index步，让pre停在下标为 index 的节点的前驱位置。然后插入，顺序依旧是“新节点的 next 先指向旧后继，再把前驱的 next 指向新节点”。

第五个接口deleteAtIndex：

void deleteAtIndex(int index) { if (index < 0 || index >= size) return; ListNode* pre = dummyHead; while (index--) { pre = pre->next; } ListNode* tmp = pre->next; pre->next = tmp->next; delete tmp; --size; }

删除的逻辑和前面 203 题完全一致，都是站在前驱视角操作。C++ 选手记得delete tmp，Java 选手交给 GC，Python 选手直接重新赋值即可。

3.4 实现中的常见坑与教训

这道题我至少见过三类翻车现场：

第一种是size忘记更新。add之后不加，delete之后不减，后面get和delete的边界判断全部错乱，而且这种 bug 非常隐蔽，单看某一个操作觉得都对，一跑完整测试序列就露馅。

第二种是插入顺序写反。node->next = pre->next; pre->next = node;这两行的顺序不能换。换成pre->next = node; node->next = pre->next;之后，node->next指向自己，链表直接成环。调试时可能会卡住，输出结果时出现无限循环。

第三种是addAtIndex里对index == size的处理。如果把条件写成index >= size，就无法在尾部插入；如果完全不校验index，index过大时pre会遍历到nullptr，然后对空指针解引用，直接崩溃。边界条件的尺度把握，正是在这类细节里锻炼出来的。

4. 206. 反转链表：最简单的题也是最经典的题

4.1 反转链表为什么是高频考点

反转链表可以说是链表题里曝光率最高的题目，没有之一。各大面试手写环节都爱出这道题，不是因为难，而是因为它能在极短代码量里考察一个人的指针控制能力、循环终止条件设计能力和对时空复杂度的理解。

这道题还有一个特点：解法非常多。迭代、递归、头插法，每一种都能写，每一种都有不同的思考方式。面试官很爱通过这道题追问“你会几种写法”，借此判断候选人是不是真的理解，而不是背题。

我见过不少同学把迭代版背得滚瓜烂熟，但一让写递归版就卡住。所以下面两种写法我都展开讲，而且会把背后的思考逻辑讲清楚，而不是只贴代码。

4.2 迭代法核心实现

迭代法的核心思想：遍历链表时，把每个节点的next指针指向前一个节点。既然当前节点的next不再指向原来的下一个节点，那原来的下一个节点就必须提前用临时变量保存，否则链表就断了。

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

三个指针各司其职：cur是当前正在处理的节点，prev是已经反转好的那部分链表的新头，nextTemp用来暂存cur原来的后继。

循环开始时，prev是nullptr，因为原链表的头节点反转后应该变成尾节点，尾节点的next就是nullptr。每次循环做四步：备份后继、翻转指针、prev前移、cur前移。循环结束后，cur变成了nullptr，prev停在原链表的最后一个节点，也就是新链表的第一个节点，所以返回prev。

注意：这里返回值千万别写成cur，循环结束时cur是空指针，返回它会让测试用例直接输出空链表。我见过不止一个人在这种细节上扣分。

很多资料喜欢用“双指针法”来命名这个解法，本质上是一样的。理解时把这幅画面记在脑子里：一个人从链表头开始走，边走边把遇到的每条路牌指向来路，最终整条路就掉了个方向。

4.3 递归法理解要点

递归版的核心是把问题分解：先反转当前节点之后的所有节点，再把当前节点接到反转后的链表尾部。

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这一步在干什么。假设链表是A -> B -> C，递归调用reverseList(B)返回的是反转后的C -> B。此时head是A，head->next是B，而B现在已经是反转链表的最后一个节点了。我们要把A接到B后面，所以让B->next = A，也就是head->next->next = head。然后A->next = nullptr，因为A是新链表的尾节点。

递归终止条件是head == nullptr || head->next == nullptr。空链表不用反转，只有一个节点的链表也不用反转，直接返回自身即可。

递归版的优点是代码极短，逻辑上也很优雅；缺点是空间复杂度是 O(n)，因为递归调用栈会占用 n 层栈帧。在实际工程里，链表长度可能达到百万级，递归深度过大可能爆栈，所以工程实践里首选迭代法。面试时可以主动提一句两个版本的时空复杂度对比，能加分。

4.4 扩展思考：反转思想可以走多远

反转链表不是孤立的知识点，它是很多更复杂问题的地基。比如“两两交换链表中的节点”，本质就是局部反转两个节点；“K 个一组反转链表”，就是先找区间、反转区间、再连接区间；“回文链表”的解法之一就是先找到中点，反转后半段，然后比较。掌握了反转的指针操作之后，这些问题都只是它在不同场景下的变体。

这道题还有第三种写法叫头插法：新建一个空头节点，遍历原链表，把每个节点依次插到新链表头部，效果等价于反转。头插法本质上利用了“头部插入元素会逆序累积”的特性，理解之后也能顺手写出反转效果。不建议作为首选解法，但它能帮助你加深对addAtHead这类操作的理解，跟我们 707 题正好呼应上了。

5. 常见问题与排错实录

5.1 空指针报错，十有八九是边界没想全

链表题最常见的运行时错误就是空指针解引用。检查点其实很固定：

• 访问cur->next前，确认cur是否可能为nullptr。
• while (cur != nullptr && cur->next != nullptr)两个条件别漏第二个。
• 删除节点前，确认被删除节点确实存在。
• 反转链表时，确认cur不为空再取cur->next。

我自己调试时有个习惯：每写一个->next，先问自己一句“当前这个节点此刻一定存在吗”。如果答案是不确定，就加前置判断。这个小习惯帮我省了很多次 Debug。

有一种不太好发现的空指针问题出现在内存释放后。C++ 里delete tmp之后，tmp变成悬空指针，如果再访问tmp->next就是非法操作。所以删除逻辑里，一定要先用一个变量保存tmp->next或者直接使用cur->next->next完成指针重连，再delete，顺序别乱。

5.2 死循环，几乎都出在指针覆盖顺序

链表死循环的锅，基本都指向两类操作。

第一类是插入时顺序写反。先执行pre->next = node，再执行node->next = pre->next，此时node->next指向了node自己，链表成环，遍历输出会无限循环。这类 bug 在本地调试时非常诡异，因为打印链表会一直输出同一个节点。

第二类是反转时cur->next被覆盖前没有保存后继。如果忘了nextTemp，反转操作执行cur->next = prev之后，原来的后继节点就找不到了，链表被腰斩，程序虽然不报错，但结果完全错误。

我对插入顺序有一个固定记忆法：“先接后面，再断前面”。新节点不是无源之水，它要先和后继建立连接，把自己安插进链条，再去修改前驱的指向。形象一点说，先让新人牵住后面人的手，再让前面的人松开旧手牵新人。

5.3 链表调试技巧与测试用例清单

刷链表题，强烈建议在本地准备一个打印链表的工具函数：

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

函数不复杂，但它能让每一道链表题的调试时间缩短一大半。每次都肉眼盯着指针看非常累，把每一步关键操作前后的链表状态打印出来，错误位置一目了然。

写测试用例时，不要只测题目给的示例。建议每条测试都跑一遍这些边界：

这些用例基本覆盖了链表题 90% 的边界雷区。把它们当成默认检查模板，每次写完直接套一遍，通过之后提交，一次过的概率会大大提高。

其实刷链表题的经验积累到一定程度，你会发现所有问题都能归纳成两个核心能力：一是能清楚说出“当前操作的目标节点的前驱是谁”，二是能写出正确的指针覆盖顺序。虚拟头节点解决的是第一个问题，临时变量和“先接后断”的口诀解决的是第二个问题。今天这三道题，本质就是在反复训练这两个能力。我自己后来做更难的两两交换、环形链表时，用的也还是这套思路，尤其是分析环的入口时，仍然得回到“快慢指针的相遇节点”和“重新从头同步遍历”这两个基本动作上。链表这东西，看着绕，但只要把基本功按今天这样的节奏打扎实，后面会越刷越顺。