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写起来最短但很多人会忘记改 sizeaddAtHead(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 0dummy-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 时间复杂度与空间复杂度的标准分析五个操作的时间复杂度原本是写题解必答的部分。这里我以哨兵节点 单向链表的实现为例操作时间复杂度说明getO(n)需要从头遍历 index 步addAtHeadO(1)直接操作 dummy-nextaddAtTailO(n)需要遍历到链表尾部addAtIndexO(n)需要先遍历到 index 位置deleteAtIndexO(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::listLeetCode 为什么还要你手写一遍这是我面试时非常喜欢问的一道衍生题。答案其实是多层次的第一层手写链表考察的是基础数据结构能力确认你理解指针操作和边界条件。第二层在更复杂的问题里比如 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 环境开启了 AddressSanitizerASan它会精确检测内存错误。如果你在 delete 节点之后又通过某个悬空指针访问了这个节点的数据就会看到heap-use-after-free报错。我在写 deleteAtIndex 时第一次踩到这个坑是在循环里顺手打印cur-val来调试而这个 cur 恰好在上一轮被 delete 了。这个错误在调试模式下特别隐蔽因为有时候内存还没被复用读出来还是原来的值看起来一切正常但 ASan 是确定性检测只要访问已释放堆内存就立刻报错。我的建议是凡是涉及手动 delete 的代码写完先自查一遍这个节点在被删除后还有没有其他指针可能访问到它。如果会说明链表没有正确摘除是 bug。6.2 输出总是比预期少一个节点或者多一个节点这类 bug 我见过最多的是出在 addAtIndex 的循环次数上。假设链表有 3 个节点你想在 index2 的位置插入即在第三个节点和 nullptr 之间插入理论上 prev 应该是第三个节点。循环条件i index会执行 2 次prev 从 dummy 走到节点 0第一个真实节点再走到节点 1第二个真实节点。等等这里是不是有问题我们想要 prev 是第三个节点索引为 2但循环只走了 2 次prev 停在了索引 1 的节点。错因为 dummy 不是真实节点所以第 1 次循环prev 从 dummy 变成节点 0对应 index0 完成第 2 次循环prev 从节点 0 变成节点 1对应 index1 完成此时插入到 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 对你来说就不再是一道题而是一类基础组件设计能力的写照。