LeetCode 上的 707 设计链表我刷过不下五遍也拿它考过不少来面试的候选人。说句实话这道题在题库里算不上一道“难题”但绝对算一道“筛人题”——能把链表基本操作一次写对、边界全覆盖、不拖泥带水的人底子通常都比较扎实。它的核心需求很朴素实现一个 MyLinkedList 链表类支持 get、addAtHead、addAtTail、addAtIndex、deleteAtIndex 五个方法。就这么五个方法我见过太多人在 index 边界判断、size 维护、尾节点更新这些地方翻车。这篇文章把我反复刷这道题的经验、两套完整代码和踩坑记录整理出来给准备面试的朋友参考也给想把手写链表彻底搞明白的初学者当一份实操笔记。1. 题目解读与解题思路分析1.1 先看清楚题目到底在考什么707 的题目描述不长要求也很直白设计一个 MyLinkedList 类实现五个方法——get(index) 获取链表中第 index 个节点的值索引无效返回 -1addAtHead(val) 在链表头部插入一个节点addAtTail(val) 在链表尾部追加一个节点addAtIndex(index, val) 在指定索引处插入节点如果 index 等于链表长度则在尾部追加如果 index 大于链表长度则不插入deleteAtIndex(index) 删除指定索引的节点索引无效则不处理。很多人刷这道题的第一反应是“这有什么难的”然后提笔就写一个单链表不带头节点遍历找前驱。写完之后跑测试用例第一组能过第二组在 index0 插入时就发现要单独处理头节点代码越补越乱最后提交一看边界用例挂了一片。这不是个例。我后来复盘总结了三个最容易出问题的点基本覆盖了这道题 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 有必要吗如果不维护 tailaddAtTail 就得从虚拟头节点一路 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 addAtTailO(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 cursize--。这里有两个重点一是 C 必须 delete释放内存二是如果删的是尾节点tail 必须更新否则 tail 指向已释放的内存后续 addAtTail 就是访问野指针程序崩溃。3.6 复杂度与空间占用一览五个方法的时间复杂度我用一个表格总结方便面试前快速过一遍方法时间复杂度说明getO(n)最坏情况取尾节点遍历全表addAtHeadO(1)直接在虚拟头节点后插入addAtTailO(1)依赖 tail 指针无需遍历addAtIndexO(n)需要先找到前驱节点deleteAtIndexO(n)需要先找到待删节点空间复杂度五个方法都是 O(1)本身不额外申请大块内存。整个链表的空间是 O(n)n 是节点数量。这里有一个容易被问到的点如果没有维护 tailaddAtTail 就是 O(n)整体性能会差一个量级这就是我在 1.3 里强调维护 tail 的原因。4. Python 版本实现与语言差异4.1 节点类与整体结构Python 刷题也是高频场景尤其面试时用 Python 写快。Python 版本不需要手动管理内存代码会短一截但要注意的坑完全不一样。class ListNode: def __init__(self, val0, prevNone, nextNone): self.val val self.prev prev self.next nextPython 的节点类用对象属性代替 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 - 1Python 版本和 C 版本逻辑一一对应只是 new 变成了 ListNode(...) 直接构造对象delete 变成了让对象失去所有引用交给垃圾回收机制处理。注意 deleteAtIndex 里最后 self.size - 1删除之后不需要像 C 那样 delete cur只要不再有变量引用它Python 的引用计数机制会自动回收内存。4.3 C 与 Python 的差异和踩坑点两种语言写同一道题能明显感受到差异。C 里最痛的是内存管理的两个点new 了必须 deletedelete 之后指针最好置空避免成为野指针而 Python 完全没有这个心智负担垃圾回收器会把无人引用的对象自动清掉。C 的优势在于性能双链表在 C 里指针操作直接、直观Python 的优势在于快速实现和调试代码量少、写起来流畅。Python 有一个 C 没有的坑需要特别提醒Python 里如果还持有待删除节点的变量引用这个节点虽然已经从链表中断开了但对象本身不会立即被回收而是等到引用计数归零才释放。在 LeetCode 的单次运行场景里这不是问题但如果拿它写长时间运行的服务就得注意把局部变量及时置为 None否则链表节点会积累在内存里。我在本地写过一个长时间跑的小工具用 Python 版链表反复删除节点内存占用一直往上涨排查了半天才反应过来是持有引用的局部变量没有被清掉。这段对比价值很高因为它帮助理解刷题语言本身的差异。做面试准备时建议至少掌握一种语言写完这道题再把另一种语言读一遍遇到面试官追问“如果换一种语言会有什么区别”不至于答不上来。5. 常见错误与排查技巧实录5.1 边界判断写错导致的行为差异这道题里三个方法的边界判断长得很像含义完全不同。我用一个对比表格把它们放在一起方法合法区间特殊处理get0 index size超出返回 -1addAtIndex0 index sizeindex size 尾插index 0 头插deleteAtIndex0 index size超出直接不操作把 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 问题最简单的方法是在每个方法入口打日志size0, opget(0) - -1 size0, opaddAtHead(1) size1, opget(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 指针的感觉完全不一样了。这也是我推荐把它作为链表练习第一道题的原因——性价比是真的高。