LeetCode 707 设计链表：虚拟头节点与边界条件全解析

LeetCode 707这道题我在好几个阶段都刷到过，每次重新做一遍都有新体会。你要是刚学数据结构，或者准备面试想快速复习链表基本功，这题几乎是必写的。题目本身叫“设计链表”，要求你实现一个MyLinkedList类，支持get、addAtHead、addAtTail、addAtIndex、deleteAtIndex这五个操作，覆盖了链表最核心的遍历、头插、尾插、指定位置插入和删除。很多人觉得这题逻辑简单，但真正下手写的时候，边界条件能把你逼疯，而且一旦用 C++ 写出内存泄漏，LeetCode 也能让你在编译阶段就“内存爆炸”。

我最早写这题用的是 C++，后来也用 Python 写过几版，还在嵌入式项目里手写过类似的无侵入链表。今天我把这题的完整拆解、踩坑记录和调试思路全部整理出来，代码部分给到可以直接粘贴运行的版本，顺带聊清楚为什么链表写得对不对，靠的不是背代码，而是对“指针到底指到哪一步”有没有精确的直觉。

1. 项目概述与题目定位

1.1 这题到底在考什么

LeetCode 707 是所有链表题里最“诚实”的一道：它不考你脑筋急转弯，也不考你花哨的算法，纯粹考你知不知道怎么用代码把“链表”这个东西实现出来。题目要求设计一个单链表类，类的内部结构、内存管理方式、边界判断全都要自己负责，LeetCode 只给你一串接口签名和预期行为。

这里要注意一个关键细节：LeetCode 的“设计链表”和我们平时在 C++ 题目里用到的ListNode* head直接操作不太一样。它更像让你模拟一个std::list的简化版，类的实例本身要持有链表的头节点和长度，然后所有操作都封装成成员函数。这题在 LeetCode 官方难度是中等，但实际难度取决于你用哪种语言和哪种实现策略——用 Python 写天然省去内存管理，用 C++ 写还要处理new/delete的配对。

考察点其实分三层：第一层是链表基本操作是否正确，第二层是边界条件是否完备（比如索引为负数、索引等于链表长度、链表为空时删除节点），第三层是代码风格和内存安全意识。很多人第一层过了，却在第三层被面试官追问到哑口无言。

1.2 适合谁刷、和其他题的关系

这题比较适合三类人来写：刚学完链表基本概念，想验证“我会不会写代码”的初学者；准备面试、想在一个小时内快速过一遍链表 API 的求职者；以及用 C++ 写底层、需要手动管理内存的开发者。我认识的一些朋友直接把 707 当作“链表基本功自测题”，写完这题再刷反转链表、环形链表、合并有序链表这些题，手感明显不一样，因为你已经知道一个链表节点是怎么被“接”到另一个节点后面的。

它和其他热门的链表题也有直接关系：707 里addAtIndex的逻辑吃透了，206 反转链表的三指针法就很好理解；707 里遍历时prev指针走多少步搞明白了，234 回文链表找中间节点就不会数错步数。也就是说，707 是所有链表题的“地基题”，值得你多写几遍，甚至刻意用不同语言写。

2. 设计思路与方案选型

2.1 为什么一定要用虚拟头节点

很多初学者写链表会直接在成员变量里保存Node* head，然后每次在头部插入、删除时都要单独写一套if (head == nullptr) ...的特殊逻辑。我第一遍写 707 的时候就是这样，代码越写越长，if分支越来越多，最后自己都分不清哪个分支在哪个场景生效。

后来我改成用虚拟头节点（dummy node），问题直接解决了一大半。虚拟头节点是一个不存实际数据的节点，它的next指向真正的第一个数据节点。类成员只维护Node* dummy和int size，所有对头部的操作都统一成“在dummy之后插入”或“删除dummy的下一个节点”，完全不需要判断链表是否为空。

这里面的道理其实很简单：链表插入和删除最难处理的永远是最前面的位置，因为常规操作需要“前驱节点”，而头节点没有前驱。虚拟头节点相当于给所有节点都配了一个前驱，让“头”不再特殊。这跟 Linux 内核链表的设计思路也是一脉相承的，后续我到第五节再展开说。你可以把dummy理解成“哨兵”，它在链表最前面站岗，让每个操作函数都走同一套代码路径，减少分支就是减少 bug。

2.2 单链表还是双链表

LeetCode 707 官方没有规定必须用单链表还是双链表。我们用单链表完全可以满足所有要求的复杂度：get、addAtIndex、deleteAtIndex都是 O(n)，addAtHead和addAtTail理论上也能做到 O(1)（尾插需要额外维护尾指针，或者通过遍历到尾部实现 O(n)）。

我建议初学者只用单链表，原因有三个。第一，单链表代码量更小，结构更清晰，重点能放在边界条件的处理上；第二，双链表的多余指针（prev）虽然能让删除更快，但会引入更多需要维护的引用关系，一旦某个prev没更新，排错成本远高于省下的那点 O(n) 遍历时间；第三，面试场景下，单链表写出来的正确率更高，你可以在代码走完后再简单提一句“如果需要频繁删除前驱节点，可以改成双向链表”，这反而是加分项。

当然，我也写过双链表版本。如果你要把 707 扩展到“支持 O(1) 删除指定节点”的场景，那就值得引入prev指针。但就这题而言，单链表是最稳妥的选择，不要为了炫技去增加复杂度。

2.3 索引语义与 size 的统一管理

这题最容易让人困惑的地方就是索引（index）的语义。LeetCode 的原题描述是：index 从 0 开始，addAtIndex中 index 等于链表长度时，插入到链表末尾；如果 index 大于链表长度，则什么都不做；如果 index 小于 0，则插入到头部；get和deleteAtIndex中 index 必须有效（0 到 size-1）。

这类规则要是不先想清楚，写出来的代码一定到处都是 bug。我建议在动笔之前，先在一张纸上写清楚有效区间：

• get(index)：只有index >= 0 && index < size才有效，否则返回 -1。
• addAtHead(val)：等价于addAtIndex(0, val)。
• addAtTail(val)：等价于addAtIndex(size, val)。
• addAtIndex(index, val)：index < 0时按 0 处理；index > size时直接 return；index == size时插到末尾；index在 [0, size) 时插到指定位置。
• deleteAtIndex(index)：只有index >= 0 && index < size才执行删除。

同时，size这个成员变量一定要在每次插入和删除时同步更新，忘了size++或size--是新手最容易犯的错误。你想想看，size就像一个仓库的账本，节点是货物，你货物进出了但账本没记，后面查库存的时候一定对不上。

3. 实操实现与核心环节拆解

3.1 C++ 完整可运行版本

直接用 C++ 写是最磨人的，因为除了逻辑，还要处理内存释放。下面这版是我后来一直用的模板，注释写得很全，你可以直接复制到 LeetCode 里跑。

struct Node { int val; Node* next; Node(int v) : val(v), next(nullptr) {} }; class MyLinkedList { private: 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-- > 0) { cur = cur->next; } return cur->val; } void addAtHead(int val) { Node* node = new Node(val); node->next = dummy->next; dummy->next = node; size++; } void addAtTail(int val) { Node* cur = dummy; while (cur->next != nullptr) { cur = cur->next; } cur->next = new Node(val); size++; } void addAtIndex(int index, int val) { if (index > size) { return; } if (index < 0) { index = 0; } Node* prev = dummy; while (index-- > 0) { prev = prev->next; } Node* node = new Node(val); node->next = prev->next; prev->next = node; size++; } void deleteAtIndex(int index) { if (index < 0 || index >= size) { return; } Node* prev = dummy; while (index-- > 0) { prev = prev->next; } Node* toDelete = prev->next; prev->next = toDelete->next; delete toDelete; size--; } };

代码看起来不多，但每个函数背后都有几个值得反复琢磨的设计决策。接下来逐个拆。

3.2 各成员函数核心逻辑拆解

get函数的核心是：先做区间判断，然后从dummy->next出发，走index步。这里有个小细节，while (index-- > 0)是先判断后自减，所以当index == 0时不会进入循环，直接返回第一个节点的值，刚好对应索引 0。这个写法比for (int i = 0; i < index; i++)更紧凑，但可读性稍差，你自己写的时候按习惯来就行，关键是别多走一步或者少走一步。

addAtHead是五个操作里最“干净”的，直接创建新节点，然后让新节点的next指向原来的头节点，再更新dummy->next。如果你用“头节点直接作为属性”的方案，这里要单独处理链表为空的情况，但有了dummy，什么都不用判断。注意顺序不能反：先node->next = dummy->next，再dummy->next = node。如果顺序反了，原来的头节点就丢了，链表会断掉。

addAtTail需要从头遍历到尾部，再从尾部插入。这里有个优化的点：如果频繁在尾部插入，可以额外维护一个tail指针，让addAtTail变成 O(1)。但为了保持代码简单，我没有加，因为addAtIndex本身就允许index == size，遍历法是统一路径。如果你追求极致性能，可以考虑维护尾指针，但注意在deleteAtIndex删除最后一个节点时要更新tail，这就引入了新的边界条件，自己权衡。

addAtIndex是最难写对的核心方法。关键在于：prev初始化为dummy，然后循环走index步。为什么是index步？因为我们要插入到“索引为 index 的节点之前”，所以需要找到索引为index - 1的节点作为前驱，也就是从dummy出发走index步（dummy本身不算索引，第一步走到索引 0，第 index 步走到索引 index-1）。比如在链表1 -> 2 -> 3中调用addAtIndex(1, 9)，我们希望得到1 -> 9 -> 2 -> 3，新节点要插到索引 1 的位置，也就是值为 2 的节点之前，那么前驱是值为 1 的节点，从dummy走 1 步刚好到达它。这一步要是没想明白，整个addAtIndex一定写出错。

deleteAtIndex的逻辑与addAtIndex类似，也是让prev走index步走到目标节点的前驱，然后执行“跳过并释放”。注意这里一定要把被删节点先保存到一个临时变量里，再更新链接，最后delete。如果你只写成prev->next = prev->next->next;，那被删节点的内存就泄漏了，虽然 LeetCode 的判题器不一定会对你的内存泄漏报错，但这在真实项目里就是事故。我见过太多人面试时写出不带delete的 C++ 链表删除，然后面试官追问“这个节点内存去哪了”时直接愣住。

3.3 时间复杂度与空间复杂度对照

这题的复杂度分析也是面试必问项，我整理成了表格方便你直接背：

空间复杂度是 O(n)，n 是链表节点数。这里有个容易混淆的点：虚拟头节点算不算空间复杂度？严格说虚拟头节点只有一个，属于常数空间，所以空间复杂度依然是 O(n)，不是 O(n+1)。

3.4 Python 版本快速留档

如果你主要用 Python 刷题，代码会短很多，因为不用手动管理内存。Python 里的对象引用自带“垃圾回收”，所以deleteAtIndex不需要也不能主动释放内存，只管把引用断开就行。

class Node: def __init__(self, val=0, next=None): self.val = val self.next = next class MyLinkedList: def __init__(self): self.dummy = Node(0) self.size = 0 def get(self, index: int) -> int: if index < 0 or index >= self.size: return -1 cur = self.dummy.next for _ in range(index): cur = cur.next return cur.val def addAtHead(self, val: int) -> None: self.dummy.next = Node(val, self.dummy.next) self.size += 1 def addAtTail(self, val: int) -> None: cur = self.dummy while cur.next: cur = cur.next cur.next = Node(val) self.size += 1 def addAtIndex(self, index: int, val: int) -> None: if index > self.size: return if index < 0: index = 0 prev = self.dummy for _ in range(index): prev = prev.next prev.next = Node(val, prev.next) self.size += 1 def deleteAtIndex(self, index: int) -> None: if index < 0 or index >= self.size: return prev = self.dummy for _ in range(index): prev = prev.next prev.next = prev.next.next self.size -= 1

Python 版本有一个小细节：Node(val, self.dummy.next)这种写法，等价于先创建Node再赋值next，我这一行就完成了。你要是第一次写，建议先用多行形式，思路更清晰，后面熟悉了再压缩。

4. 常见问题与调试排查实录

4.1 我实际踩过的三个坑

第一次提交 707 的时候，我自认为逻辑完美，结果连续三次提交都有用例过不了。复盘之后发现全是一些很“低级”但很典型的错误，分享出来给你避坑。

第一个坑：只处理了插入和删除逻辑，忘了更新size。有一次我在addAtIndex里加了size++，但在addAtHead里忘了加，然后get的时候索引完全错乱，链表明明有 5 个节点，size却还是 4，最后一个节点永远访问不到。这个问题的排查方法很简单：写一个辅助函数打印size和链表所有元素，跑几个用例，马上就能看出账目对不上。

第二个坑：删除头节点时，dummy的指向没更新。我用的是带dummy的实现，按理说不会踩这个坑，但有一次我改代码时不小心在deleteAtIndex里写成了if (index == 0) { dummy = dummy->next; delete dummy; }，这等于把dummy本身给删了，直接导致后续访问崩溃。正确的做法永远是通过prev找前驱再删除，而不是动dummy本身。

第三个坑：addAtIndex中index == size的情况没单独想清楚。当时我写的是先判断if (index > size) return;，然后让prev走index步。在index == size的场景下，prev会从dummy一直走到dummy->next == nullptr的最后一个节点的前一个位置？不对，其实是走到最后一个节点本身。这里没法靠猜，必须画图验证。

4.2 画图 + 打印调试法

链表调试最忌讳空想，我强烈建议你准备纸笔，或者用电脑上的画图工具，把节点和指针一个个画出来。以deleteAtIndex(1)为例，假设链表是dummy -> 1 -> 2 -> 3：你先标出谁是prev，从dummy走 1 步到节点 1，然后要删的是节点 2，因此执行prev->next = prev->next->next，这时代码里的指针关系是1.next = 3，然后delete 2。画一遍图之后你会发现，指针操作本质上就是“改箭头的指向”，根本不用背代码。

写代码的时候，我建议在局部范围先写一个调试辅助函数：

void printList() { Node* cur = dummy->next; while (cur != nullptr) { cout << cur->val << " -> "; cur = cur->next; } cout << "NULL, size=" << size << endl; }

然后在每个操作函数的前后调用它，看看链表形态是否符合预期。这比打断点更直观，因为你看到的是一整条链的全貌，而不是某个局部变量的值。

4.3 常见报错与排查速查表

我把常见的运行时报错和对应的排查方向整理成表，你对照着检查会省很多时间：

还有一个很隐蔽的坑：while (index-- > 0)这个写法虽然简洁，但如果你在循环体内部又对index做了修改，那就乱了。所以循环里千万别动index，它只是个“步数计数器”。我以前在图省事时把index--和prev = prev->next写在一行，结果逻辑混乱，后来老老实实分开写，一眼就能看清楚。

5. 从 707 延伸到真实场景

5.1 循环单链表、双向链表、链表逆序的扩展

热词里出现了“循环单链表”“单循环链表”“逆置链表”“基于链表的两个集合的差集”这些内容，都和 707 高度相关。如果你 707 写完还有余力，建议把这三个变种都看看。

循环单链表指的是尾节点的next不再指向nullptr，而是指回头节点。它的好处是可以从任意节点出发遍历整个链表，但坏处是遍历的终止条件变了，不再是cur == nullptr，而是cur == 起始节点。在 707 的代码基础上改造循环单链表，很容易的一个玩法是：把尾节点接到dummy上而不是nullptr，然后addAtTail和addAtHead就变成了对称操作，很有意思。

双向链表就是在每个节点多加一个prev指针，插入和删除时要同时维护两个方向的引用。热词里“c++结构体链表基本语法”往往就要求你能同时定义单链和双链的结构体。我建议你在 707 之后手动写一遍双链表，重点体会“先接后断”的原则：插入新节点时，先把新节点的next和prev都接好，再断开旧链接，这样能防止中间状态出现悬空指针。

链表逆序（逆置链表）是另一类高频题。它的核心思想是三个指针：prev、cur、next，每次把cur->next指回prev，然后三个指针整体后移。707 里你已经在addAtIndex和deleteAtIndex中反复练习了prev指针的移动，再做逆序题时会容易很多。

5.2 嵌入式 / 内核链路中的链表代码示例

热词里“嵌入式链表代码示例”值得多说一句。在主流的嵌入式内核（比如 Linux kernel、RT-Thread）里，链表与 707 里的“数据节点带next指针”有一个重要的结构差异：它们用的是侵入式链表。

所谓侵入式，就是链表节点结构体list_head被嵌入到你自己的业务结构体里，而不是让业务结构体“继承”链表的指针字段。用代码表示：

struct list_head { struct list_head *next, *prev; }; struct my_data { int value; struct list_head list; // 链表节点嵌入到业务结构体 };

使用时通过list_entry/container_of宏，从list_head的地址反推出整个my_data结构体的地址。这种设计的好处是一个链表节点可以同时挂到多个链表上（比如同时挂到哈希表和 LRU 链表），而且不强制数据的组织方式。你要是从 707 的直接指针实现切到侵入式链表，刚开始会很不适应，因为cur->next返回的不再是你的数据节点，而是一个list_head，你必须再用container_of才能拿到业务数据。但正是这种思路，让 Linux 内核的链表操作无比灵活。

707 题里练好的“前驱节点插入”“删除节点”这些基本功，在侵入式链表里完全通用，唯一要变的是指针类型的转换。所以我一直觉得，刷好 707 这类基础题，再去看内核链表的源码，绝对事半功倍。

5.3 刷题与面试建议

关于 707 的刷法，我自己的建议是至少写三遍：第一遍用 Python，先把逻辑理顺，避免被内存管理干扰；第二遍用 C++，重点练内存释放和指针操作；第三遍给自己限时 15 分钟，看看能不能一次写对、不靠调试。三遍下来，链表的基本功基本就焊死了。

面试中如果遇到这题，面试官通常不只问“能不能跑通”，还会追问几个延伸问题：你的addAtIndex时间复杂度是多少；为什么用虚拟头节点；deleteAtIndex在 C++ 里怎么避免内存泄漏；如果链表特别长，get操作频繁，怎么优化。这些问题我在前面的章节都覆盖到了，你最好能把原因讲出来，而不是只背答案。我个人体会是，能把边界条件讲得清清楚楚的候选人，比能闷头写完五道题的候选人更受欢迎，因为这代表你真的理解了数据结构在做什么。

回到这题本身，LeetCode 707 刷完最大的价值不是会做这道题，而是你真正建立起了一个“链表操作肌肉记忆”：什么情况下需要前驱节点，如何维护 size，如何统一头尾插入。这些肌肉记忆会在你处理 LRU Cache、并查集、图论邻接表的时候反复被调用。我现在自己在写嵌入式代码里的链表时，最常用的还是 707 里练出来的那套手法——先画图、再动指针、最后验证边界。希望你也能通过这题，把链表彻底拿捏。