企业官网建设流程全解析

LeetCode 上的 707 设计链表，我刷过不下五遍，也拿它考过不少来面试的候选人。说句实话，这道题在题库里算不上一道“难题”，但绝对算一道“筛人题”——能把链表基本操作一次写对、边界全覆盖、不拖泥带水的人，底子通常都比较扎实。它的核心需求很朴素：实现一个 MyLinkedList 链表类，支持 get、addAtHead、addAtTail、addAtIndex、deleteAtIndex 五个方法。就这么五个方法，我见过太多人在 index 边界判断、size 维护、尾节点更新这些地方翻车。这篇文章把我反复刷这道题的经验、两套完整代码和踩坑记录整理出来，给准备面试的朋友参考，也给想把手写链表彻底搞明白的初学者当一份实操笔记。

1. 题目解读与解题思路分析

1.1 先看清楚题目到底在考什么

707 的题目描述不长，要求也很直白：设计一个 MyLinkedList 类，实现五个方法——get(index) 获取链表中第 index 个节点的值，索引无效返回 -1；addAtHead(val) 在链表头部插入一个节点；addAtTail(val) 在链表尾部追加一个节点；addAtIndex(index, val) 在指定索引处插入节点，如果 index 等于链表长度则在尾部追加，如果 index 大于链表长度则不插入；deleteAtIndex(index) 删除指定索引的节点，索引无效则不处理。

很多人刷这道题的第一反应是“这有什么难的”，然后提笔就写一个单链表，不带头节点，遍历找前驱。写完之后跑测试用例，第一组能过，第二组在 index=0 插入时就发现要单独处理头节点，代码越补越乱，最后提交一看，边界用例挂了一片。这不是个例。我后来复盘总结了三个最容易出问题的点，基本覆盖了这道题 90% 的失分原因。

第一个是边界条件。addAtIndex 里 index 等于链表长度时要尾插、index 小于 0 时要头插，这两个语义和 deleteAtIndex 的“索引无效不处理”完全不同，非常容易写混。第二个是 size 的维护。链表类自带的 size 字段，每次成功插入和删除都必须同步更新，多分支结构里漏掉一个分支的更新，索引判断立马失效。第三个是内存管理。写 C/C++ 时删除节点必须显式释放内存，LeetCode 不会直接报编译错，但面试官一句“你这个节点删了之后内存呢？”就能把人问住。

1.2 为什么我推荐直接上双链表加虚拟头节点

题目没有规定必须用单链表还是双链表，也没有规定是否带头节点。但从工程角度，我强烈建议直接实现双链表，并且使用虚拟头节点，也就是 dummy node。这不是炫技，而是用少量空间换逻辑正确性。

先说不带头节点的问题。链表为空时 head 是空指针，第一次插入节点时得写 head = new Node(val)；删除头节点时得写 head = head->next。这两种情况在代码里都属于特殊分支，需要额外 if 判断。头插、尾插、中间插入都要围绕 head 是否为空、操作位置是否为头来区分逻辑，代码会膨胀出一堆条件判断，出错率直线上升。而虚拟头节点的思路，是在真正的头节点前面放一个不存储有效数据的哨兵节点，构造时初始化 dummyHead->next = nullptr。这样一来，链表永远不会“空”——至少还有一个虚拟头节点垫底，所有插入操作都统一成“在某个节点后面插入”，所有删除操作都统一成“删除某个节点的后继”，头节点这个特殊情况直接消失。

再说单链表和双链表的取舍。单链表做删除时需要找到待删节点的前驱，只能从头遍历；双链表因为每个节点都有 prev 指针，删除当前节点时可以直接通过 cur->prev 拿到前驱，O(1) 拿到前后关系。这个差异在这道题里感受不深，因为查找节点本身就要 O(n) 遍历，但往后的 206 反转链表、138 复制带随机指针的链表这些题，双链表的 prev 思路会反复用到。我练习时的体会是：先把双链表写熟，再回头看单链表，很多操作的理解会通透很多。

1.3 类成员变量的设计选择

MyLinkedList 类里需要三个成员：虚拟头节点指针、尾节点指针、当前链表长度。虚拟头节点前面说过了；size 是为了让 get、deleteAtIndex 的索引校验变成 O(1) 的“查表操作”，不用遍历才知道链表多长；tail 指针则是为了把 addAtTail 从 O(n) 降到 O(1)。

很多人会问：tail 有必要吗？如果不维护 tail，addAtTail 就得从虚拟头节点一路 next 到尾，每次都要 O(n) 遍历。LeetCode 没有强制时间复杂度，但工程师的习惯是把明显能优化掉的成本优化掉。维护 tail 的代价是：头插、中间插入、删除节点时都要判断“操作位置是否影响 tail”，多几个 if 分支。代价不大，收益明显。我在第一次写这道题时偷懒没维护 tail，后面测大数据量用例时 addAtTail 明显慢，改成 tail 之后整体代码也就多写了十来行。这道题的场景里，我建议维护，划重点。

2. 数据结构选型与节点定义

2.1 C++ 的节点结构体怎么写

C++ 版本我用结构体定义节点，构造函数里把所有指针成员显式初始化：

struct Node { int val; Node* next; Node* prev; Node(int x) : val(x), next(nullptr), prev(nullptr) {} };

这里有个新手很容易踩的坑：只写 int val 和 Node* next 两个成员，不写构造函数，然后创建节点时只赋值 val，忘记初始化 next。这么做的后果是 next 指向一个随机的内存地址，遍历链表时程序直接段错误。所以在构造函数里把 next 和 prev 都置空，是必须的、不是可选的。C 语言里有人用 malloc 分配节点，同样也要记得 node->next = NULL，否则后果一样。

2.2 类成员的初始化

class MyLinkedList { private: Node* dummyHead; Node* tail; int size; public: MyLinkedList() { dummyHead = new Node(-1); tail = dummyHead; size = 0; } };

这一步的关键在于 dummyHead 创建之后，一定要把 tail 也指向 dummyHead。因为链表为空时，虚拟头节点的下一个节点为空，而“尾节点”就是虚拟头节点自己。漏掉这行，后面 addAtTail 在空链表上的第一次操作就会把 tail 变成野指针，或者让 tail 一直指向 nullptr，运行到一半才发现空指针访问。这个初始化顺序要写死在构造里，每次 new 完都这样配，形成肌肉记忆。

2.3 五种 API 的实现顺序

我建议按“依赖从简单到复杂”的顺序来实现：先 get，再 addAtHead，再 addAtTail，再 deleteAtIndex，最后 addAtIndex。这样做的原因是 get 的逻辑最独立，写完就能立刻跑最小用例验证构建的链表是否正确；addAtHead 和 addAtTail 分别是头、尾两个极端的插入，搞定了这两端，中间插入就只剩“找到位置再操作”这一步；deleteAtIndex 和 addAtIndex 的很多边界逻辑相似，先写删除，插入时就能复用经验。

3. C++ 完整实现与逐段代码注释

3.1 get：从虚拟头节点出发

int get(int index) { if (index < 0 || index >= size) { return -1; } Node* cur = dummyHead->next; for (int i = 0; i < index; i++) { cur = cur->next; } return cur->val; }

两处细节。一是边界判断要同时考虑下界和上界，index < 0 和 index >= size 都是无效索引，直接返回 -1。二是遍历使用 for 循环，虽然 while (index--) 也能跑，但 for 循环里 index 没有被修改，逻辑上更清晰。第一次刷题的话，建议统一用 for 循环，少一个“变量被改掉”的隐性坑。get 的时间复杂度是 O(n)，最坏情况是取最后一个节点的值，要一路遍历到尾部；空间复杂度是 O(1)，没有额外分配。

3.2 addAtHead：四步指针操作

void addAtHead(int val) { Node* newNode = new Node(val); newNode->next = dummyHead->next; if (newNode->next) { newNode->next->prev = newNode; } else { tail = newNode; } dummyHead->next = newNode; newNode->prev = dummyHead; size++; }

头插的核心是“把新节点挂在虚拟头节点后面”。四步分别对应：新节点的 next 指向原第一个节点；原第一个节点的 prev 指回新节点；虚拟头节点的 next 指向新节点；新节点的 prev 指向虚拟头节点。这里最容易漏的是 if 分支——如果原链表为空，newNode->next 是 nullptr，就不会有“原第一个节点的 prev 指回新节点”这一步，但此时 tail 必须更新成 newNode。如果不更新，后续 addAtTail 就会在错误的 tail 后面追加节点，链表结构直接乱掉。头插的时间复杂度是 O(1)，这正是链表相对于数组插入的巨大优势。

3.3 addAtTail：O(1) 的秘密

void addAtTail(int val) { Node* newNode = new Node(val); tail->next = newNode; newNode->prev = tail; tail = newNode; size++; }

为什么只有五行？因为 tail 一直维护着真正的尾节点，所以尾插就是一次指针连接和一次 tail 自己的更新。对比不维护 tail 的版本，addAtTail 要先遍历到尾，代码变成：

Node* cur = dummyHead; while (cur->next) cur = cur->next;

然后再插入，整体 O(n)。差距在链表很长时非常明显。这里有一个需要注意的点：如果在 addAtHead 里漏掉了空链表分支，tail 仍然是 dummyHead，那么这里插入时 tail->next 指向了 newNode，实际上产生了第二个节点链接，完全错了。调试的时候这种问题最隐蔽，因为代码不报错，但遍历结果就少节点或者多节点。

3.4 addAtIndex：最考验细节的方法

void addAtIndex(int index, int val) { if (index > size) { return; } if (index < 0) { index = 0; } Node* cur = dummyHead; for (int i = 0; i < index; i++) { cur = cur->next; } Node* newNode = new Node(val); Node* nextNode = cur->next; newNode->next = nextNode; newNode->prev = cur; cur->next = newNode; if (nextNode) { nextNode->prev = newNode; } else { tail = newNode; } size++; }

第一步边界判断：index > size 直接 return，注意这里是“大于”而非“大于等于”，因为 index == size 时是合法的尾部追加。第二步：index < 0 时置为 0，实现头插。这也是和 deleteAtIndex 最大的区别，后面会专门对比。第三步找到前驱节点，循环结束后 cur 就是待插入位置的前驱。第四步连接新节点：这里有个顺序技巧——先把新节点的 next 和 prev 都赋值好，再修改旧节点的指针。这样不会出现中间状态下链表断裂或者指错。最后，如果 nextNode 为空，说明插在尾部，tail 要更新。

这段代码是五个方法里信息量最大的，值得多写几遍，每一遍都会有不同的理解。我第一次写时把 index > size 写成了 index >= size，导致 addAtIndex(size, val) 被当成非法操作直接 return，尾插功能废了半个。后来检查用例才发现，index == size 时本来就应该允许插入到末尾，判断条件多一个等号，行为就完全不同。

3.5 deleteAtIndex：别忘了删除和更新

void deleteAtIndex(int index) { if (index < 0 || index >= size) { return; } Node* cur = dummyHead->next; for (int i = 0; i < index; i++) { cur = cur->next; } Node* prevNode = cur->prev; Node* nextNode = cur->next; prevNode->next = nextNode; if (nextNode) { nextNode->prev = prevNode; } else { tail = prevNode; } delete cur; size--; }

这里和 addAtIndex 的边界判断完全相反：index == size 时，addAtIndex 是合法操作，deleteAtIndex 是非法操作，因为索引是从 0 开始，最后一个节点的索引是 size - 1。所以我一直建议把这两个方法连在一起写，同时思考，避免搞混。

删除的核心也很直接：找到待删节点 cur，用 prevNode 和 nextNode 把它夹住，然后让 prevNode->next = nextNode，如果 nextNode 存在，让 nextNode->prev = prevNode，否则说明删掉的是尾节点，tail 要改为 prevNode。最后 delete cur，size--。这里有两个重点：一是 C++ 必须 delete，释放内存；二是如果删的是尾节点，tail 必须更新，否则 tail 指向已释放的内存，后续 addAtTail 就是访问野指针，程序崩溃。

3.6 复杂度与空间占用一览

五个方法的时间复杂度我用一个表格总结，方便面试前快速过一遍：

空间复杂度五个方法都是 O(1)，本身不额外申请大块内存。整个链表的空间是 O(n)，n 是节点数量。这里有一个容易被问到的点：如果没有维护 tail，addAtTail 就是 O(n)，整体性能会差一个量级，这就是我在 1.3 里强调维护 tail 的原因。

4. Python 版本实现与语言差异

4.1 节点类与整体结构

Python 刷题也是高频场景，尤其面试时用 Python 写快。Python 版本不需要手动管理内存，代码会短一截，但要注意的坑完全不一样。

class ListNode: def __init__(self, val=0, prev=None, next=None): self.val = val self.prev = prev self.next = next

Python 的节点类用对象属性代替 C++ 的指针，本质还是引用。构造函数把 prev 和 next 都设为 None，避免出现未初始化的悬空引用。C++ 里的“指针必须初始化”，在 Python 里就对应“引用必须指向 None 或具体对象”，同样重要。

4.2 实现代码与逐行解释

class MyLinkedList: def __init__(self): self.dummy_head = ListNode(0) self.tail = self.dummy_head self.size = 0 def get(self, index: int) -> int: if index < 0 or index >= self.size: return -1 cur = self.dummy_head.next for _ in range(index): cur = cur.next return cur.val def addAtHead(self, val: int) -> None: new_node = ListNode(val) new_node.next = self.dummy_head.next if new_node.next: new_node.next.prev = new_node else: self.tail = new_node self.dummy_head.next = new_node new_node.prev = self.dummy_head self.size += 1 def addAtTail(self, val: int) -> None: new_node = ListNode(val) self.tail.next = new_node new_node.prev = self.tail self.tail = new_node self.size += 1 def addAtIndex(self, index: int, val: int) -> None: if index > self.size: return if index < 0: index = 0 cur = self.dummy_head for _ in range(index): cur = cur.next new_node = ListNode(val) next_node = cur.next new_node.next = next_node new_node.prev = cur cur.next = new_node if next_node: next_node.prev = new_node else: self.tail = new_node self.size += 1 def deleteAtIndex(self, index: int) -> None: if index < 0 or index >= self.size: return cur = self.dummy_head.next for _ in range(index): cur = cur.next prev_node = cur.prev next_node = cur.next prev_node.next = next_node if next_node: next_node.prev = prev_node else: self.tail = prev_node self.size -= 1

Python 版本和 C++ 版本逻辑一一对应，只是 new 变成了 ListNode(...) 直接构造对象，delete 变成了让对象失去所有引用，交给垃圾回收机制处理。注意 deleteAtIndex 里最后 self.size -= 1，删除之后不需要像 C++ 那样 delete cur，只要不再有变量引用它，Python 的引用计数机制会自动回收内存。

4.3 C++ 与 Python 的差异和踩坑点

两种语言写同一道题，能明显感受到差异。C++ 里最痛的是内存管理的两个点：new 了必须 delete，delete 之后指针最好置空，避免成为野指针；而 Python 完全没有这个心智负担，垃圾回收器会把无人引用的对象自动清掉。C++ 的优势在于性能，双链表在 C++ 里指针操作直接、直观；Python 的优势在于快速实现和调试，代码量少、写起来流畅。

Python 有一个 C++ 没有的坑需要特别提醒：Python 里如果还持有待删除节点的变量引用，这个节点虽然已经从链表中断开了，但对象本身不会立即被回收，而是等到引用计数归零才释放。在 LeetCode 的单次运行场景里这不是问题，但如果拿它写长时间运行的服务，就得注意把局部变量及时置为 None，否则链表节点会积累在内存里。我在本地写过一个长时间跑的小工具，用 Python 版链表反复删除节点，内存占用一直往上涨，排查了半天才反应过来是持有引用的局部变量没有被清掉。

这段对比价值很高，因为它帮助理解刷题语言本身的差异。做面试准备时，建议至少掌握一种语言写完这道题，再把另一种语言读一遍，遇到面试官追问“如果换一种语言会有什么区别”，不至于答不上来。

5. 常见错误与排查技巧实录

5.1 边界判断写错导致的行为差异

这道题里，三个方法的边界判断长得很像，含义完全不同。我用一个对比表格把它们放在一起：

把 addAtIndex 和 deleteAtIndex 的边界摆在一起看，区别就很清楚了。addAtIndex 是“可以等于 size”的，delete 是“必须小于 size”的。我在代码评审里看过很多人把 addAtIndex 的 index > size 写成 index >= size，导致永远无法在末尾追加节点；也看过把 deleteAtIndex 的 index >= size 写成 index > size，导致删除最后一个节点时越界访问。这类问题用肉眼排查耗时很久，但用测试用例覆盖却能快速暴露：分别调用 addAtIndex(size, val) 和 deleteAtIndex(size - 1)，马上就能看出问题。

5.2 size 没更新的典型症状

size 是索引判断的核心依据。每个分支都要保证 size 更新，但现实是，代码里很容易漏。典型场景是在 addAtIndex 里判断 index > size 直接 return 的分支，如果忘记 return 而走到了继续执行，就会在越界位置插入，size 还加了 1，链表长度和实际不符，后续所有操作全部错乱。

排查 size 问题最简单的方法，是在每个方法入口打日志：

size=0, op=get(0) -> -1 size=0, op=addAtHead(1) size=1, op=get(0) -> 1

日志一打，size 错在哪一步立刻清楚。本地调试跑一段脚本，把五个方法的操作序列打出来，对照预期结果，很快就能定位是哪个分支漏了 size 更新。这种方法比盯着代码干想效率高得多。我不建议直接跳过日志去猜 bug，链表题最忌讳“盲改”，越改越乱。

5.3 尾指针悬垂和内存泄漏

尾指针悬垂是最难查的一类问题。常见场景是：删除最后一个节点后，tail 还指向被删除的节点，此时 tail->prev 是野指针，下一次 addAtTail 直接崩溃；或者头插到空链表时没有更新 tail，导致 addAtTail 把节点挂到了虚拟头节点后面，链表里出现两个头。这类问题光靠读代码很难发现，因为平时的用例可能覆盖不到“空链表插入”“删除尾节点”这些边界。

对策是准备一个“操作序列用例”，专门覆盖所有边界情况：空链表 get、空链表 delete、头插到尾插交替、addAtIndex(0) 后删除 0、删除唯一节点。跑完这个用例，尾指针问题基本无处可藏。内存泄漏则不同，C++ 里 delete 漏掉会表现为内存只增不减，跑大数据量用例时明显变慢甚至内存超限。面试时虽然没有工具让你查泄漏，但代码里 delete 缺失和 delete 后未置空都是减分项，写的时候就要养成习惯：删除节点固定写两行，delete cur 然后 cur = nullptr，形成模板。

5.4 调试链表的实用技巧

我强烈建议在类里加一个 debugPrint 方法，刷题阶段保留即可，提交前删掉或者注释掉：

void debugPrint() { Node* cur = dummyHead->next; cout << "size=" << size << ": "; while (cur) { cout << cur->val << " "; cur = cur->next; } cout << endl; }

每次操作结束时调用一次，打印链表长度和所有节点值，就能直观看到每一步操作之后链表长什么样。遇到问题先看哪一步开始和预期不一致，再定位那个方法。这个方法花不了两分钟，但对理解链表行为帮助极大。我现在带新人时都会让他们加一行 debugPrint，比自己闭门造车快太多。

6. 从这道题延伸出去的经验

6.1 链表题目中的通用思维

707 这道题把链表操作的基本功都过了一遍：插入要管前后指针、删除要管前驱后继、边界要分情况讨论。把这些想明白了，后面很多题都是同一个思路。比如反转链表，本质就是不断改 next 指针方向；合并有序链表，本质就是选择较小节点并维护尾指针；判断链表是否有环，快慢指针只是工具，核心还是理解链表的连接关系。我刷链表题的经验是：不要急着套模板，先把每个操作在纸上画一遍，指针怎么变、哪些节点会受影响，画完再写代码，正确率高很多。

6.2 面试官喜欢追问的几个点

把 707 写完之后，面试官大概率会追问这些问题。第一，“为什么用虚拟头节点？”答：为了统一头节点的处理逻辑，避免空链表和头节点操作的边界判断。第二，“addAtTail 为什么是 O(1)？”答：因为维护了 tail 指针，不需要遍历找到尾部。第三，“如果不用双链表，用单链表怎么实现 deleteAtIndex？”答：单链表需要找前驱节点，时间复杂度同样是 O(n)，但代码里要维护一个 prev 指针跟随 cur 前进，找到待删节点时 prev 正好是它的前驱。第四，“如果这是一个并发环境，怎么保证链表操作线程安全？”这题会把话题引向锁、原子操作和读写分离，属于进阶问题。

6.3 相关题目练习路径参考

我建议顺着下面的路径把链表题练一遍：先做 707 设计链表，把增删改查写熟；再做 206 反转链表，练习单链表指针反转；然后做 21 合并两个有序链表，练习双指针和尾插；再做 141 环形链表，理解快慢指针；最后做 138 复制带随机指针的链表，练习哈希表和链表综合操作。这几道题做完，链表相关的面试题基本就覆盖了大半。每道题都可以从单链表和双链表两个角度去写一遍，收获完全不是只刷一遍能比的。这道题刷完之后，你对链表的理解会明显不同，再去看循环单链表、双向循环链表这些变体，只需要理解环形结构里“尾的 next 指向头”这一个差异，其他操作都是相通的。

我自己在实际刷这道题时最大的体会是：链表题的难点从来不是“知道怎么做”，而是“做的时候能一次想全所有角落”。五个操作，每个操作对应一组边界，每一组边界都要踩一遍、错一遍、再改一遍，才会真正长在脑子里的肌肉记忆里。707 恰好把这点浓缩在一个题目里，代码量不大，信息密度却极高。刷完它再去写 206 反转链表、21 合并有序链表，你会发现对 next 和 prev 指针的感觉完全不一样了。这也是我推荐把它作为链表练习第一道题的原因——性价比是真的高。