1. 这道题到底在考什么：别被"简单题"标签骗了
LeetCode 707（设计链表）在题库里的难度标的是简单，但我面试过不少人，也带过团队刷题，结论恰恰相反——这是一道翻车率极高的"简单题"。原因很简单：它不考你懂不懂链表，考的是你在没有任何IDE提示、没有模板代码、没有现成链表类的情况下，能不能把最基础的数据结构从零写对、写稳、写全。三道代码题里面，用这道题当第一道筛选的公司我都见过，而且挂的人比挂中等难度题的人还多。
题目要求本身很直白：设计一个链表，支持get、addAtHead、addAtTail、addAtIndex、deleteAtIndex这五个方法，而且索引从 0 开始。但"直白"和"简单"是两回事。真正动手写的时候你会发现，坑全藏在边界条件里：addAtIndex里index == size是合法操作，index > size才是非法操作；deleteAtIndex传进来的索引可能落在最后一个节点上；用循环遍历找节点的时候，循环次数差一次整个逻辑就全崩。这些细节，光靠"理解链表是啥"是搞不定的，你得实际写过、错错过，才能形成肌肉记忆。
而且说实话，这道题的另一个价值在于：它是为数不多的、让你从零实现一个类的题目。平时刷题都是直接拿现成的ListNode结构体用，但 707 要求你连头节点、size、哨兵节点这些基础设施自己搭。这个"搭积木"的过程，恰恰是工程上写 LRU Cache、写跳表、写数据库 B+ 树节点管理时会反复用到的基本功。所以这篇博客我不打算只贴一份能过的代码，我想把五个操作逐一拆开，讲清楚每个边界条件为什么这么判，讲清楚不同实现方案的取舍，最后再聊聊我在面试和刷题过程中踩过的那些坑。
2. 数据结构选型：哨兵节点、单链表还是双链表
2.1 为什么强烈建议加一个哨兵节点
很多人第一次写 707 的时候，会直接维护一个head指针，然后所有操作都围绕这个指针展开。这种写法不是不能过，但代码里会出现大量if (head == nullptr)这种判空逻辑，而且很容易写出 bug。举个例子，删除头节点的时候，你得特殊处理：让head = head->next，再释放旧节点。这个分支忘写，LeetCode 就给你一个空指针异常。
我个人的习惯是：加一个哨兵节点（dummy head）。也就是说，链表里永远有一个"幽灵节点"存在，head不是指向第一个真实节点，而是指向这个哨兵节点，真实节点都挂在哨兵节点后面。这样做的好处是：头节点和普通节点在操作逻辑上完全统一了，插入、删除都不需要再单独照顾"操作位置是头部"这种情况。
用生活化的类比来说：如果你在一个没有 0 号门牌的小区里送快递，每一栋楼你都要看一眼是不是第一栋，多累；如果每栋楼都有一个统一的编号规则，你只管按规则找就行了。哨兵节点就是这个"统一编号规则"。它的值是无意义的（我一般初始化为 0 或者不初始化），它存在的唯一意义就是让链表的边界情况不再特殊。
2.2 单向链表和双向链表的取舍
707 题解里，很多人会用双向链表来实现，理由是 LeetCode 的官方题解也是 double linked list 版本，而且评论区很多人在讨论 prev 和 next 两个指针的维护。但我个人建议，第一次做这道题，用单向链表就够了。
原因有两点。第一，这道题的所有操作都只给了索引，没要求反向遍历或者找前驱节点，单向链表只要多维护一个prev指针（用来记录当前遍历到的节点的前一个节点），就能完成所有增删操作。双向链表当然也可以，但两个指针的交接逻辑更复杂，写的时候多一倍的指针操作，出错概率也高一倍。第二，面试的时候，面试官问"你怎么不用双向链表"，你可以说"我考虑到题目的 indexing 操作并不需要反向访问，所以选择更简单的单向链表以降低出错概率；如果有需要经常倒序遍历的场景，我再加 prev 指针"。这个回答本身就是加分项，显示了你在做工程取舍，而不是在背题。
当然，如果你已经对单向链表非常熟练，想挑战更复杂的写法，双向链表也完全可以，但我想提醒你：别为了炫技增加不必要的复杂度。刷题和面试的核心是"在限定时间内正确解决一个工程问题"，写一个冗长复杂的版本不如写一个简洁可靠的版本。
2.3 核心数据结构怎么定义
不管用哪种方案，代码里都需要先定义链表节点。很多人习惯直接用struct或class定义，我建议直接用struct，因为默认公开，省得写public:。节点里存两个东西：val和next指针。构造函数顺便把值初始化好。
struct Node { int val; Node* next; Node(int x) : val(x), next(nullptr) {} };然后 MyLinkedList 类里维护两个成员变量：size（真实节点数量）和dummy（哨兵节点）。size不是可选项，是必须项。后面你会看到，所有涉及index合法性判断的逻辑，都依赖size。你可以在每次操作的时候遍历链表数长度，但那样时间开销会多一个 O(n)，而且代码更绕。工程上这种做法叫"空间换时间"，用一个 int 存大小，换取每个操作 O(1) 的长度判断。
class MyLinkedList { private: Node* dummy; int size; public: MyLinkedList() { dummy = new Node(0); size = 0; } // ... 五个操作 };这里我要多说一句：很多人问构造函数里要不要把 dummy 初始化。要，必须要。不初始化的话 dummy 是个野指针，后面所有操作访问 dummy->next 都会出问题。而且初始化一个值是多少不重要，重要的是它必须是一个合法的 Node 对象。
3. 五个操作的边界条件逐个拆解：写对每一处判断
3.1 get：最容易踩的二分查找式误区
get(index)要求返回链表中第index个节点的值。如果索引无效，返回 -1。这个操作看起来最简单，但很多人会在两个地方出错。
第一个错误是边界判断写错。正确写法是：if (index < 0 || index >= size) return -1;。index >= size是重点。链表的节点索引是 0 到size-1，所以当index == size时已经越界了。如果你写成index > size - 1，在size == 0的时候就会得到index > -1，这时候如果调用get(-1)也会被放进来，最终导致访问无效内存。
第二个错误是遍历步数不对。假设链表有 3 个真实节点，要取index = 2的值，也就是第三个节点。很多人会这么写：
Node* cur = dummy->next; while (index--) { cur = cur->next; } return cur->val;这段代码在index = 2的时候，第一次循环让 cur 从节点 0 走到节点 1，第二次循环从节点 1 走到节点 2，然后返回节点 2 的值。看起来对，但它能过的原因只是碰巧。更通用的写法是用 for 循环：
Node* cur = dummy->next; for (int i = 0; i < index; i++) { cur = cur->next; } return cur->val;两种写法的区别在于对"走几步"的表达是否清晰。for + 步数变量的写法，你能直观看到走的是index步；而while(index--)的写法容易让人混淆"走 index 步"和"走到第 index 个"。我建议统一用 for 循环，排查问题的时候一眼就能看出逻辑。
3.2 addAtHead：写起来最短，但很多人会忘记改 size
addAtHead(val)要求在头部插入一个节点。有了哨兵节点，这个操作就变成：新建节点，让新节点的 next 指向dummy->next，然后让dummy->next指向新节点。然后，size++。
注意，最后这步size++我见过至少三个候选人漏掉。漏掉 size 的结果是：插入一个节点后，size还是 0，后续addAtIndex(0, val)会被判断为合法（因为index >= size没法触发），然后新节点被插到头部，整个链表的顺序和你预期完全不一致。这是那种"代码能编译、部分测试能过、但逻辑有潜伏病"的典型错误。
你可能觉得奇怪：addAtHead不是直接用dummy->next操作吗，为什么还需要 size？对，插入操作本身确实不依赖 size，但插入之后的维护必须依赖 size 被正确更新。任何时候都不应该觉得"这次操作没用到某个变量就忘了更新它"。
void addAtHead(int val) { Node* newNode = new Node(val); newNode->next = dummy->next; dummy->next = newNode; size++; }这里还有个细节：newNode->next = dummy->next这行必须写在dummy->next = newNode之前。你要是反着写，等于先把 dummy 的 next 覆盖成新节点，然后再把新节点的 next 指向自己，链表直接形成环。这个顺序问题，很多新手第一次写都会踩。我建议把这行代码背下来，而且知道为什么顺序不能反。
3.3 addAtTail：最简单的操作，但别忽略空链表的情况
addAtTail(val)要求追加到尾部。有了 size 之后，最简单的做法是：遍历到最后一个真实节点，然后把新节点接上去。判断条件是：
Node* cur = dummy; while (cur->next != nullptr) { cur = cur->next; } cur->next = new Node(val); size++;这里cur从 dummy 开始，而不是从dummy->next开始。为什么？如果链表是空的（size == 0），dummy->next是 nullptr，从 dummy 开始的话 while 循环一次都不执行，直接就把新节点挂在 dummy 后面了。这就是哨兵节点统一头尾操作的体现：空链表和非空链表用的是同一套代码。
当然，还有一个更高效的写法，如果你在设计类的时候额外维护一个tail尾指针，addAtTail可以做到 O(1)。但我不建议在 707 里面这么做，因为addAtIndex和deleteAtIndex都会改变尾节点，你要在每处增删操作后同步维护 tail 的状态，复杂度上升不少，而这道题的性能要求并没有严格到必须让 addAtTail 从 O(n) 降到 O(1)。工程里"能跑就行"和"跑得最快"之间要有个取舍，竞赛/面试场景里，优先保证正确性和可维护性。
3.4 addAtIndex：全题最蛋疼的边界条件，没有之一
addAtIndex(index, val)在指定索引处插入节点。如果index等于链表的长度，则说明新节点是链表的尾节点。如果index大于链表长度，则不插入；如果 index 小于 0，则在头部插入。
我先把 LeetCode 原题里这段英文原文的边界定义贴出来，因为它非常容易让人产生误解。我曾见过好几个候选人理解成"index == size 的时候也应该是非法操作，因为索引最大是 size-1"——这个理解是错的。在原题的语义里，addAtIndex的 index 不是"要访问的节点索引"，而是"新节点要插入的位置"。位置比节点索引多一个概念：位置 0 是头部之前，位置 size 是尾部之后。
所以合法性判断是：
if (index > size) return; // 非法 if (index < 0) index = 0; // 非法负索引，统一视为头部插入插一句：LeetCode 原题这里说的是"如果 index 小于 0，则在头部插入"，所以你要处理这个负索引的情况。很多人会直接写if (index < 0 || index > size) return;，这在严格意义上和题目描述不一致。题目允许负 index 存在并把它当成 0 处理。LeetCode 的测试用例确实会有addAtIndex(-1, val)的例子吗？有，我看过相关题解下有人反馈。所以建议你还是老老实实把负 index 纠正为 0。
然后是定位插入位置：
Node* prev = dummy; for (int i = 0; i < index; i++) { prev = prev->next; } Node* newNode = new Node(val); newNode->next = prev->next; prev->next = newNode; size++;仔细看这个循环次数：当 index = 0 的时候，循环 0 次，prev 就是 dummy，新节点插入到头部，正确。当 index = size 的时候，循环 size 次，prev 会从 dummy 一路走到最后一个真实节点，新节点插入到最后，正确。这就是为什么上面的合法性判断是index > size才 return，因为index == size时插入位置存在，只是正好在末尾。
我把这个边界单独拎出来讲，是因为它是 707 里最容易写错的地方，而且它几乎是 LeetCode 官方和评论区反复讨论的核心考点。你甚至可以把它当成一道脑筋急转弯来理解："addAtIndex 的 index 是位置，不是节点下标；位置的范围是 0 到 size（含两端）。"
3.5 deleteAtIndex：比插入简单的删除，删尾节点时留意指针
deleteAtIndex(index)删除指定索引的节点。如果 index 无效，则什么都不做。合法性判断比较简单：
if (index < 0 || index >= size) return;注意这里是>=，因为删除针对的是"第几个节点"，索引范围只能是 0 到 size-1，不存在"删除位置"这种语义。
定位要删节点的前驱：
Node* prev = dummy; for (int i = 0; i < index; i++) { prev = prev->next; } Node* toDelete = prev->next; prev->next = toDelete->next; delete toDelete; size--;这里有个 C++ 特有的坑：delete toDelete会不会因为"toDelete 是最后一个节点、next 是 nullptr"而崩溃？不会。C++ 的 delete 只是释放当前节点占用的内存，不会递归去 delete 它的 next 指针。所以你可以放心地把toDelete->next置空后再 delete（其实不置空也行，节点内部保存的野指针在被释放后不再被访问，就没事）。但为了养成好习惯，我一般写成：
Node* toDelete = prev->next; prev->next = toDelete->next; delete toDelete;顺序很重要：先把 toDelete 从链表里摘除（prev->next = toDelete->next），然后再 delete。你要是先 delete，再改 prev->next，那就是访问已释放的内存，直接 undefined behavior。
另外提醒一下：如果你的面试环境用的是 Java/Python，内存回收由 GC 处理，不需要手动 delete。但如果是 C/C++，一定要记得释放。面试官会盯着这个看，手动管理内存的场景下，这属于"安全问题"级别的错误。
4. 从力扣答题到工程思考：复杂度、内存管理和面试追问
4.1 时间复杂度与空间复杂度的标准分析
五个操作的时间复杂度原本是写题解必答的部分。这里我以哨兵节点 + 单向链表的实现为例：
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| get | O(n) | 需要从头遍历 index 步 |
| addAtHead | O(1) | 直接操作 dummy->next |
| addAtTail | O(n) | 需要遍历到链表尾部 |
| addAtIndex | O(n) | 需要先遍历到 index 位置 |
| deleteAtIndex | O(n) | 需要先遍历到 index 的前驱位置 |
| 空间复杂度 | O(n) | 每个节点存储 val 和 next 指针 |
面试官如果问"为什么 get 是 O(n) 而不是 O(1)？"，你要能答出来：链表不像数组，元素在内存里不连续，不能通过首地址 + 偏移量直接拿到第 index 个元素，只能顺着 next 指针一步步走。这也是数组和链表最本质的区别。有时候面试官会顺着问："那如果经常需要随机访问，你会选数组还是链表？"你如果说"那数组更合适，因为随机访问是 O(1)"，这就说明你真理解数据结构选型的逻辑，而不是只会背 API。
4.2 内存碎片和节点分配：一个在 LeetCode 上看不出来的问题
在 LeetCode 上用new Node(val)创建节点，提交后能过，因为在线判题系统不在乎你 new 了多少次、有没有频繁分配小对象。但如果你把这个设计搬到实际工程里，就有讲究了。
链表节点是一个典型的小对象（通常 16 字节左右，如果对齐可能更大）。频繁地 new/delete 小对象，会导致两个问题：一个是内存碎片，一个是性能抖动。你看数据库、操作系统内核里的链表实现，很多用"内存池"或者"分配器"来管理节点，正是为了缓解这些问题。
所以当你跟面试官聊完基本实现后，如果能补充一句："这种逐节点 new 的实现在生产环境里一般会用内存池优化，因为链表的增删会高频触发小对象分配，容易产生碎片"，这不卖弄，而是展示你把 LeetCode 题和工程实践连起来了。这个点最难能可贵，大多数候选人的答案只停留在"我写完了，代码能过"，并不会往下想一层。
4.3 面试追问：为什么不用 STL 的 list，或者 std::vector
"既然 C++ 有现成的 std::list，LeetCode 为什么还要你手写一遍？"这是我面试时非常喜欢问的一道衍生题。答案其实是多层次的：
- 第一层：手写链表考察的是基础数据结构能力，确认你理解指针操作和边界条件。
- 第二层：在更复杂的问题里（比如 LRU Cache、DJ 算法、图邻接表），没有现成的链表能直接满足需求，你需要基于链表改造出自己的结构，这时候手写能力就是刚需。
- 第三层：std::list 是双向链表，有额外的 prev 指针，如果你只需要单向遍历逻辑，用 std::list 会浪费内存和 cache 局部性。
所以，707 的正确刷法不是"我调 STL 一次通过就完了"，而是"我手写了一遍，理解了每种操作的指针变化，再去看 STL 的实现，看它怎么处理迭代器失效、怎么做内存管理"。
5. 一个值得写进注释的细节：为什么索引判断需要用 size
写完五个操作，你可以回头整体看一眼：所有边界条件都和size有关。这也解释了为什么我一开始就强调必须在类里维护size变量。
有些人会问：为什么不直接遍历链表数长度？原因很实际：数长度本身是 O(n)，如果你在每个操作里都数一遍，所有操作都会从 O(n) 变成 O(2n)，常数翻倍；更重要的是代码变得极其冗长。维护size的代价只是每次增删操作多加一行size++ / size--，收益却是所有合法性判断都变成 O(1) 的常数时间，这个买卖很划算。
工程里有一个更普遍的原则叫"避免重复计算"。凡是能在状态变化时同步维护的元数据，就不要在每次查询时重新计算。比如缓存，比如维护用户会话数，比如 HashMap 里的 size 字段，全是这个思路。707 虽然只是一道题，但它让我第一次真正体会到"用字段换时间"的甜蜜。
6. 刷题过程中的常见报错实况：空指针、输出错序、泄漏三连
6.1 "AddressSanitizer: heap-use-after-free" 是怎么回事
LeetCode 的 C++ 环境开启了 AddressSanitizer（ASan），它会精确检测内存错误。如果你在 delete 节点之后，又通过某个悬空指针访问了这个节点的数据，就会看到heap-use-after-free报错。
我在写 deleteAtIndex 时第一次踩到这个坑，是在循环里顺手打印cur->val来调试，而这个 cur 恰好在上一轮被 delete 了。这个错误在调试模式下特别隐蔽，因为有时候内存还没被复用，读出来还是原来的值，看起来一切正常；但 ASan 是确定性检测，只要访问已释放堆内存就立刻报错。我的建议是：凡是涉及手动 delete 的代码，写完先自查一遍"这个节点在被删除后，还有没有其他指针可能访问到它"。如果会，说明链表没有正确摘除，是 bug。
6.2 输出总是比预期少一个节点或者多一个节点
这类 bug 我见过最多的是出在 addAtIndex 的循环次数上。假设链表有 3 个节点，你想在 index=2 的位置插入（即在第三个节点和 nullptr 之间插入），理论上 prev 应该是第三个节点。循环条件i < index会执行 2 次，prev 从 dummy 走到节点 0（第一个真实节点），再走到节点 1（第二个真实节点）。等等，这里是不是有问题？我们想要 prev 是第三个节点（索引为 2），但循环只走了 2 次，prev 停在了索引 1 的节点。错，因为 dummy 不是真实节点，所以：
- 第 1 次循环：prev 从 dummy 变成节点 0（对应 index=0 完成）
- 第 2 次循环：prev 从节点 0 变成节点 1（对应 index=1 完成）
此时插入到 prev->next，也就是节点 1 和节点 2 之间，索引等于 2 的位置。正确。很多人会卡在这个推理上：dummy 占据了一个"虚拟位置"，导致循环步数和索引之间的关系不是直观的i <= index，而是i < index。我的解决办法是：在草稿纸上画链表，从 dummy 标上位置编号，再推演一次。画图比背结论可靠得多。
6.3 测试用例"addAtHead 之后再 get(0) 返回不对"
这种问题十有八九是 size 没更新。假设你 addAtHead 之后 size 还是 0，然后调用 get(0)，合法性判断index >= size会变成0 >= 0，直接判定越界，返回 -1。你插入了一个元素，却取不到，让人当场懵圈。修法很简单：所有增删操作检查一遍 size 是否同步更新。我习惯在写完整个类之后，逐个操作检查"影响 size 的语句都有了吗"，这个习惯帮我避免了很多次隐性 bug。
7. 完整参考实现：单向链表版与可延伸思路
最后给出一份我常用的 C++ 参考实现，基于哨兵节点 + size 字段，五个操作全部覆盖。你可以直接照着敲一遍，然后尝试改成 Java/Python 版本。
struct Node { int val; Node* next; Node(int x) : val(x), 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; for (int i = 0; i < index; i++) { cur = cur->next; } return cur->val; } void addAtHead(int val) { Node* newNode = new Node(val); newNode->next = dummy->next; dummy->next = newNode; 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; for (int i = 0; i < index; i++) { prev = prev->next; } Node* newNode = new Node(val); newNode->next = prev->next; prev->next = newNode; size++; } void deleteAtIndex(int index) { if (index < 0 || index >= size) return; Node* prev = dummy; for (int i = 0; i < index; i++) { prev = prev->next; } Node* toDelete = prev->next; prev->next = toDelete->next; delete toDelete; size--; } ~MyLinkedList() { Node* cur = dummy; while (cur != nullptr) { Node* next = cur->next; delete cur; cur = next; } } };注意最后面的析构函数：我顺手补了一个遍历释放全部内存的析构。LeetCode 的判题不会因为你析构写不写而判错，但工程上必须写，否则就是内存泄漏。如果你把这个类的实现贴给面试官看，析构函数的存在本身就是一个加分细节，说明你养成了"谁分配谁释放，分配释放成对"的习惯。
后续想深入的话，你可以做三件事：第一，把单向链表改成带尾指针的版本，对比 addAtTail 的复杂度变化；第二，改成双向链表版，体会 prev 指针维护的复杂度和调试成本；第三，把整个类迁移到 C 语言，用 malloc/free 手动管理内存，会发现 C 语言没有任何智能指针帮你兜底，每一步都得更谨慎。做完这三件事，707 对你来说就不再是一道题，而是一类"基础组件设计"能力的写照。
