企业官网建设流程全解析

先问一个可能让不少刷题人不好意思承认的问题：你第一次写力扣707的时候，是不是也以为把五个空方法填完就结束了。实际上这道题名字叫“设计链表”，翻译成大白话就是：自己实现一个包含增删查的链表类。它不涉及什么高深的算法套路，也不用背某个现成模板，但链表最容易踩的坑，几乎全被它集中塞进了五个接口里。很多人写完以后一脸懵，跑测试发现 get 越界、加在末尾失败、删除第一个节点后链表整个消失，最后只能对着代码逐行查。

这篇内容就是围绕这道题，把从选型、实现、测试到扩展的完整思路写清楚。它适合刚开始刷链表题的人看，也适合准备面试前想快速复盘链表细节的读者。我会按照我自己写这道题时的习惯来组织：先读懂题面边界，再决定用单链表还是双链表，然后逐方法拆实现，最后用用例清单把自己锤一遍。整个过程中最重要的不是“把代码跑通”，而是把每个边界条件的来龙去脉讲清楚。

1. 读懂题面里的隐含条件：五个接口对应三类边界

1.1 接口清单与它们的真实意图

先把题目翻译成一份功能清单，避免后面写偏：

• get(index)：返回链表第 index 个节点的值，索引无效返回 -1。
• addAtHead(val)：在头部插入一个值为 val 的节点。
• addAtTail(val)：在尾部追加一个值为 val 的节点。
• addAtIndex(index, val)：在第 index 个节点之前插入新节点。index 等于链表长度时追加到末尾；index 大于链表长度时不插入；index 小于 0 时按头部插入处理。
• deleteAtIndex(index)：删除第 index 个节点，索引无效则什么都不做。

单独看每个方法都不难，但它们的行为空间其实都卷在 index 和 size 这两个变量上。get 和 delete 主要用越界判断，addAtIndex 用的是“大于 length 不操作、等于 length 追加、小于 0 头插”这套逻辑。最容易犯错的地方往往不是某一个分支写不出来，而是五个方法之间的处理规则并不完全一致，复制粘贴时会把 index 小于 0 的处理方式一并抄错。

1.2 为什么这道题考的是“边界意识”

链表和数组最大的直觉差异是：数组你喜欢用下标，链表你只能用“走几步”来实现下标访问。题目没有提供“直接跳到第 index 个节点”的魔法，你只能靠循环遍历先找到前驱，所以边界条件注定会密集出现。

空链表上的第一个 addAtTail 其实等价于头插；size 为 1 的链表删除第 0 个节点后，再调用 get(0) 必须返回 -1；addAtIndex(5, val) 在一个长度为 3 的链表上是静默无效操作。如果一开始没有把这些边界全部列出来，就很容易写出测试样例能过、隐藏用例全挂的代码。我每次看到有人提交后抱怨“为什么隐藏用例这么变态”，心里都会想，其实所有边界都写在题干里了，只是没逐句拆开。

2. 选型决定一半成败：我为什么锁定“单链表 + 哨兵节点”

2.1 别用数组应付“设计链表”

刷题时总有人想走捷径：用 C++ 的 vector 或 Java 的 ArrayList 封装一个带索引的类，代码确实短，很多用例甚至也能过。但直到面试官追问“链式存储体现在哪”，你才会发现这套做法根本没碰链表。

707 设计链表的目的是让写题人亲手维护节点之间的 next 指针，用数组包装的做法丢掉了这个练习价值。我在指导 A 同学时也发现，他先用 vector 蒙混过关，去面试遇到白板写链表反转时直接卡壳，因为脑海里根本没有“节点之间通过指针串联”的图景。所以第一版还是老老实实定义 ListNode，实现真正由节点串起来的数据结构。

2.2 单链表和双向链表：不是越复杂越好

双向链表每个节点多一个 prev 指针，删除已知节点时可以更轻松地拿到前驱，听起来更高端。但对 707 来说，deleteAtIndex 本身要先按 index 遍历到目标节点，遍历已经是 O(n)，前驱能不能通过 prev 直接拿到，并没有改变总复杂度。

再加上插入和删除时都要维护两组指针，出现错误的概率也随之翻倍。单链表把这些额外负担全部去掉，只留一个 next，逻辑最精简，刚好足够撑起这道题需要的增删查能力。等单链表写顺了，再升级成双链表反而容易得多，因为你已经知道所有指针操作的核心顺序：先保住后继，再改变前驱。

2.3 哨兵节点的核心价值：让空链表和普通链表共用一套逻辑

最终选型里真正让我舒服的不是链表本身，而是“哨兵节点”这个结构。简单说，我在真正的第一个节点前放一个 dummy 节点，它不存业务数据，只占位。这样空链表并不真的空，它还有一个 dummy 节点指向空指针。

这个结构带来一个很实际的收益：addAtHead 时不需要单独修改头指针，deleteAtIndex(0) 也走和删除中间节点完全相同的代码路径。没有哨兵时，每次插入删除几乎都逃不掉“if (head == nullptr)”这类特判；有了哨兵，特殊分支被直接合并成普通逻辑。代价不过是一个节点的内存，收益却是代码从几个分支变成一条直线。这笔账我每次和面试官聊选型时都会算一遍。

3. 核心实现拆解：每个方法都可以从画图开始解释

3.1 完整实现：先给出一版可以直接提交的 C++ 代码

这里给出一版我认为最顺手、也最适合复盘的 C++ 实现。C++ 的 new 和 delete 能把链表节点的生命周期讲得更明确，对理解内存管理也有帮助。

struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} }; class MyLinkedList { private: ListNode *dummy; int size; public: MyLinkedList() : dummy(new ListNode(0)), size(0) {} int get(int index) { if (index < 0 || index >= size) return -1; ListNode *cur = dummy->next; while (index--) { 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 < 0) index = 0; if (index > size) return; ListNode *prev = dummy; while (index--) { prev = prev->next; } ListNode *node = new ListNode(val); node->next = prev->next; prev->next = node; ++size; } void deleteAtIndex(int index) { if (index < 0 || index >= size) return; ListNode *prev = dummy; while (index--) { prev = prev->next; } ListNode *tmp = prev->next; prev->next = tmp->next; delete tmp; --size; } ~MyLinkedList() { ListNode *cur = dummy; while (cur) { ListNode *next = cur->next; delete cur; cur = next; } } };

这套代码里最核心的套路就一句话：从 dummy 出发走 index 步，得到目标节点的前驱。后面每个方法的分析，都建立在这句话上。

3.2 get 的定位逻辑：为什么从哨兵的下一个节点开始走

get(index) 第一件事是越界检查，if (index < 0 || index >= size) return -1;这两行几乎是我在所有操作方法里最早写下来的。因为边界判断一旦漏掉 size，后续遍历很可能会访问空指针或野指针。

定位时使用ListNode *cur = dummy->next;，然后让 cur 往前走 index 步。原因很简单：dummy 不占索引位，真正的第 0 个节点挂在 dummy 后面。假设链表是 1->2->3，要取 index=2 的节点，cur 从节点 1 出发，走两步到节点 3，正好返回 3。有人会纠结为什么不是 index+1，答案是目标节点本身也算在出发后的步数里，从第 0 个节点出发，不需要再额外多走一步。

同理，插入删除时如果 prev 从 dummy 出发走 index 步，它就会停在目标节点的前驱上。这一步是整个定位逻辑的核心，画一张图就能看得非常清楚。

3.3 addAtIndex 的前驱定位和插入顺序

addAtIndex 是五个方法里最需要画图的一个。处理负数之后，先判断if (index > size) return;。注意是大于而不是大于等于，因为 index 等于 size 时要追加，属于合法操作。

然后让 prev 从 dummy 出发走 index 步，指向目标位置的前驱。接下来插入新节点的顺序必须是：

node->next = prev->next; prev->next = node;

不能反过来。反过来的瞬间，prev->next 已经被新节点覆盖，你再也拿不到原来的后继节点，后半段链表直接丢失。addAtHead 写成addAtIndex(0, val)，addAtTail 写成addAtIndex(size, val)，本质上就是复用这套定位逻辑：index=0 时前驱就是 dummy，index=size 时前驱是最后一个节点，尾部追加天然成立。这样写比单独维护两个特判方法省心得多，因为维护成本被压缩到了 addAtIndex 一处。

3.4 deleteAtIndex 与 C++ 的内存释放

删除和插入共用前驱定位：从 dummy 出发走 index 步，prev 指向待删节点的前驱，tmp = prev->next就是待删节点。先把 prev->next 接到 tmp->next 上，再把 tmp delete 掉。

这里的陷阱有两个。第一个是有人忘了 delete tmp，虽然判题环境不一定立刻崩溃，但代码本身存在内存泄漏。第二个是有人会写prev->next = prev->next->next;，这样逻辑上勉强说得通，但被断开的节点指针已经没保存了，想 delete 都找不到地址。正确做法永远是把临时节点先保存下来，再改指针，最后释放。

3.5 顺手写个析构函数，别把坏习惯留给真实项目

力扣上单个测试用例结束以后进程会退出，不写析构函数通常不影响判题，但我还是习惯把释放整个链表的循环写上。思路是每次保存当前节点的 next，再 delete 当前节点，一直走到空指针为止。这样一来，多个测试用例复用同一个类时，内存也不会越积越多。这个习惯练顺手以后，写真实项目里的资源管理代码时就不容易犯低级错误。

4. 踩得最多的三个坑：断链、定位过头、size 不更新

4.1 插入时先接后继，再改前驱，顺序是最容易出错的地方

我在代码注释里写过一句话：先让新节点去握原来后继的手，再由前驱指向新节点。因为这一步的出错率远高于其他任何环节。

可以类比婚礼迎宾过程：新节点想进队，必须先和后面的人对齐，然后再让前面的人把位置交接给它。如果前驱先指向新节点，后面的人就彻底找不到了，队伍后半截直接从眼前消失。很多同学调试半天没发现问题，打了日志才发现链表从插入点开始只剩两个节点在互相指，这才意识到是顺序写反了。我建议把“插之前先想清楚，原来的后继会不会因为这次操作而丢失”作为链表操作的肌肉记忆。

4.2 定位循环多走一步或少走一步，边界表现完全不同

遍历定位时最常出现的错误，一类是把for (int i = 0; i < index; ++i)写成i <= index，导致指针多走一步，在最后一个节点上继续访问 next 得到空指针。另一类是把 index 先减一再做判断，比如while (--index)，可读性很差，而且边界含义模糊。

我推荐统一使用while (index--)，它天然对应“从 dummy 出发走 index 步”的语义。index=0 时一步不走，index=size 时会走到最终的空节点之前，刚好用来做尾部追加。不过要注意这是 C++ 里后置自减特有的写法，翻译成 Java 或 Go 时最好改成 for 循环，避免歧义。

4.3 size 不同步更新，整个类的地基就塌了

五个方法里最容易忽视的其实是 size。如果写完增删方法却忘了维护它，典型现象是：刚加入第一个节点后，立刻 get(0) 返回 -1；addAtTail 永远插在错误位置；deleteAtIndex 有时删掉的是前一个节点。原因很简单，所有 index 判断都建立在 size 上，size 一错，前面的边界保护全部失效。

我习惯在每次 add 和 delete 方法的最后单独写一行大小变更，并且在本地调试函数里直接打印 size，让 size 和实际遍历到的节点长度反复对照。另外要注意 addAtTail 委托addAtIndex(size, val)时，传入的必须是没有加 1 的旧长度。不要在 addAtTail 里面先给 size 加 1 再调用 addAtIndex，否则 addAtIndex 内部会用错误的长度判断越界，所有行为都会变调。

4.4 addAtIndex 的负数规则和 deleteAtIndex 不一样

中文版题面通常把 addAtIndex 中的负数情况写得很明确：index 小于 0 时在头部插入。而 deleteAtIndex 遇到负数应该直接返回。这两个规则不一样，但很多人习惯性地用同一个if (index < 0) index = 0;去套 delete，结果在负数删除用例上产生意料之外的“删掉第 0 个节点”行为。

最稳的做法是：add 之前单独判断负数并转成头部插入；delete 之前用if (index < 0 || index >= size) return;直接退出。两个方法各写各的边界，不要共用一段修复 index 的逻辑。这个细节虽然只有两行，却是在面试中经常被追问的点。

5. 用用例清单把边界全部按出来：我自己的自测方法

5.1 先把题目自带的示例完整走一遍

题目给的标准操作序列是：

我建议你不要只对着输出看结果，而是把每一步的链表状态写出来，尤其要标出 dummy 节点在哪个位置。很多边界 bug 在纸上推演一遍就能暴露，因为你会强制自己思考“这一步的前驱到底是谁”。

5.2 自建一组最小边界用例，别放过空链表和越界

只跑官方样例远远不够。我在本地测试里会放一组更小的用例，专门锤边界。下面这段可以用编译器的 assert 快速验证：

MyLinkedList list; assert(list.get(0) == -1); list.addAtIndex(0, 1); assert(list.get(0) == 1); list.deleteAtIndex(0); assert(list.get(0) == -1); MyLinkedList list2; list2.addAtTail(5); assert(list2.get(0) == 5); MyLinkedList list3; list3.addAtHead(1); list3.addAtHead(2); list3.addAtHead(3); assert(list3.get(0) == 3); assert(list3.get(2) == 1); MyLinkedList list4; list4.addAtIndex(-1, 7); assert(list4.get(0) == 7); list4.addAtIndex(1, 8); list4.addAtIndex(2, 9); assert(list4.get(2) == 9); list4.addAtIndex(3, 10); // index > size，应该被忽略 assert(list4.get(2) == 9);

这些用例覆盖了空链表操作、头部连续插入、负数索引、尾部追加和非法索引忽略。把这段放到 main 函数里编译运行一次，五个方法的正确性就有了基本保障。

5.3 打印链表：最快定位到底是哪步破坏了结构

最有效的调试手段是在类里加一个 dump 方法，把 size 和每个节点的值打出来：

void dump() { ListNode *cur = dummy->next; cout << "size=" << size << " : "; while (cur) { cout << cur->val << " -> "; cur = cur->next; } cout << "null" << endl; }

每次增删操作后调用一次 dump，你就能在运行结果里直观看到链表被破坏的位置。比如插入顺序写反时，dump 会打印出只有一两个节点在自指；size 忘更新时，size 的数值和实际打印的节点数会对不上。案子上看不出来的问题，跑两次 dump 基本都能定位到具体哪一行。

6. 复杂度账本和现实延伸：707 练完还有什么价值

6.1 用一张表看懂各类实现差在哪

单链表加哨兵版本完成以后，最大的收获其实是建立起一张复杂度账本：

从这张表能看懂一个重要结论：链表真正的优势是固定位置插入删除时不需要搬移元素，代价是随机访问能力弱。707 里所有操作都按索引执行，所以单链表整体表现平平，但真实项目里“从头遍历”和“从中间插入”往往不在同一个热点路径上，数据结构的选择必须结合场景。

6.2 链表和哈希表配合的典型场景

现在的面试题里，链表很少单独出现，它经常和哈希表等结构组合成实用算法。比如 LRU 缓存淘汰策略的经典做法，就是哈希表 O(1) 找节点，双向链表 O(1) 调整优先级；跳表则是在链表上增加多级索引，用空间换时间；哈希冲突里的拉链法，本质上也是在数组桶后面挂链表。把 707 里面的“维护 next、维护位置、处理边界”练扎实，再去看这些场景的代码，会发现核心还是那段前驱后继操作。

6.3 从 707 延伸出来的下一步练习

我给自己的要求是，写完单链表版以后再做三个改造：第一，给链表加一个尾指针，让尾部追加真正达到 O(1)；第二，把代码改成双向链表，比较删除和移动节点时的代码量变化；第三，把数据类型从 int 改成模板，让这个类能持有任意类型的数据。这三个改造做完以后，707 就不再是一个需要背的模板，而是你自己的基础设施。

我在刷这一题时的个人体会是：不要只满足于提交通过，而是把 addAtIndex 画成图，把每一步指针变化都讲给别人听。后来碰到各种链表衍生题，我也会下意识地在草稿纸上先画 dummy，再画目标节点和前驱，这个习惯就是写 707 养成的。每次敲完一段指针操作，都会多确认一遍：这次操作会不会让 size 和真实节点数脱节？这条 next 现在指向的节点还能不能通过遍历访问到？如果说刷题有什么实质收获，对我而言不是某个具体答案，而是对数据结构一致性这种敏感度。