LeetCode 707这道题我在好几个阶段都刷到过每次重新做一遍都有新体会。你要是刚学数据结构或者准备面试想快速复习链表基本功这题几乎是必写的。题目本身叫“设计链表”要求你实现一个MyLinkedList类支持get、addAtHead、addAtTail、addAtIndex、deleteAtIndex这五个操作覆盖了链表最核心的遍历、头插、尾插、指定位置插入和删除。很多人觉得这题逻辑简单但真正下手写的时候边界条件能把你逼疯而且一旦用 C 写出内存泄漏LeetCode 也能让你在编译阶段就“内存爆炸”。我最早写这题用的是 C后来也用 Python 写过几版还在嵌入式项目里手写过类似的无侵入链表。今天我把这题的完整拆解、踩坑记录和调试思路全部整理出来代码部分给到可以直接粘贴运行的版本顺带聊清楚为什么链表写得对不对靠的不是背代码而是对“指针到底指到哪一步”有没有精确的直觉。1. 项目概述与题目定位1.1 这题到底在考什么LeetCode 707 是所有链表题里最“诚实”的一道它不考你脑筋急转弯也不考你花哨的算法纯粹考你知不知道怎么用代码把“链表”这个东西实现出来。题目要求设计一个单链表类类的内部结构、内存管理方式、边界判断全都要自己负责LeetCode 只给你一串接口签名和预期行为。这里要注意一个关键细节LeetCode 的“设计链表”和我们平时在 C 题目里用到的ListNode* head直接操作不太一样。它更像让你模拟一个std::list的简化版类的实例本身要持有链表的头节点和长度然后所有操作都封装成成员函数。这题在 LeetCode 官方难度是中等但实际难度取决于你用哪种语言和哪种实现策略——用 Python 写天然省去内存管理用 C 写还要处理new/delete的配对。考察点其实分三层第一层是链表基本操作是否正确第二层是边界条件是否完备比如索引为负数、索引等于链表长度、链表为空时删除节点第三层是代码风格和内存安全意识。很多人第一层过了却在第三层被面试官追问到哑口无言。1.2 适合谁刷、和其他题的关系这题比较适合三类人来写刚学完链表基本概念想验证“我会不会写代码”的初学者准备面试、想在一个小时内快速过一遍链表 API 的求职者以及用 C 写底层、需要手动管理内存的开发者。我认识的一些朋友直接把 707 当作“链表基本功自测题”写完这题再刷反转链表、环形链表、合并有序链表这些题手感明显不一样因为你已经知道一个链表节点是怎么被“接”到另一个节点后面的。它和其他热门的链表题也有直接关系707 里addAtIndex的逻辑吃透了206 反转链表的三指针法就很好理解707 里遍历时prev指针走多少步搞明白了234 回文链表找中间节点就不会数错步数。也就是说707 是所有链表题的“地基题”值得你多写几遍甚至刻意用不同语言写。2. 设计思路与方案选型2.1 为什么一定要用虚拟头节点很多初学者写链表会直接在成员变量里保存Node* head然后每次在头部插入、删除时都要单独写一套if (head nullptr) ...的特殊逻辑。我第一遍写 707 的时候就是这样代码越写越长if分支越来越多最后自己都分不清哪个分支在哪个场景生效。后来我改成用虚拟头节点dummy node问题直接解决了一大半。虚拟头节点是一个不存实际数据的节点它的next指向真正的第一个数据节点。类成员只维护Node* dummy和int size所有对头部的操作都统一成“在dummy之后插入”或“删除dummy的下一个节点”完全不需要判断链表是否为空。这里面的道理其实很简单链表插入和删除最难处理的永远是最前面的位置因为常规操作需要“前驱节点”而头节点没有前驱。虚拟头节点相当于给所有节点都配了一个前驱让“头”不再特殊。这跟 Linux 内核链表的设计思路也是一脉相承的后续我到第五节再展开说。你可以把dummy理解成“哨兵”它在链表最前面站岗让每个操作函数都走同一套代码路径减少分支就是减少 bug。2.2 单链表还是双链表LeetCode 707 官方没有规定必须用单链表还是双链表。我们用单链表完全可以满足所有要求的复杂度get、addAtIndex、deleteAtIndex都是 O(n)addAtHead和addAtTail理论上也能做到 O(1)尾插需要额外维护尾指针或者通过遍历到尾部实现 O(n)。我建议初学者只用单链表原因有三个。第一单链表代码量更小结构更清晰重点能放在边界条件的处理上第二双链表的多余指针prev虽然能让删除更快但会引入更多需要维护的引用关系一旦某个prev没更新排错成本远高于省下的那点 O(n) 遍历时间第三面试场景下单链表写出来的正确率更高你可以在代码走完后再简单提一句“如果需要频繁删除前驱节点可以改成双向链表”这反而是加分项。当然我也写过双链表版本。如果你要把 707 扩展到“支持 O(1) 删除指定节点”的场景那就值得引入prev指针。但就这题而言单链表是最稳妥的选择不要为了炫技去增加复杂度。2.3 索引语义与 size 的统一管理这题最容易让人困惑的地方就是索引index的语义。LeetCode 的原题描述是index 从 0 开始addAtIndex中 index 等于链表长度时插入到链表末尾如果 index 大于链表长度则什么都不做如果 index 小于 0则插入到头部get和deleteAtIndex中 index 必须有效0 到 size-1。这类规则要是不先想清楚写出来的代码一定到处都是 bug。我建议在动笔之前先在一张纸上写清楚有效区间get(index)只有index 0 index size才有效否则返回 -1。addAtHead(val)等价于addAtIndex(0, val)。addAtTail(val)等价于addAtIndex(size, val)。addAtIndex(index, val)index 0时按 0 处理index size时直接 returnindex size时插到末尾index在 [0, size) 时插到指定位置。deleteAtIndex(index)只有index 0 index size才执行删除。同时size这个成员变量一定要在每次插入和删除时同步更新忘了size或size--是新手最容易犯的错误。你想想看size就像一个仓库的账本节点是货物你货物进出了但账本没记后面查库存的时候一定对不上。3. 实操实现与核心环节拆解3.1 C 完整可运行版本直接用 C 写是最磨人的因为除了逻辑还要处理内存释放。下面这版是我后来一直用的模板注释写得很全你可以直接复制到 LeetCode 里跑。struct Node { int val; Node* next; Node(int v) : val(v), 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; while (index-- 0) { cur cur-next; } return cur-val; } void addAtHead(int val) { Node* node new Node(val); node-next dummy-next; dummy-next node; 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; while (index-- 0) { prev prev-next; } Node* node new Node(val); node-next prev-next; prev-next node; size; } void deleteAtIndex(int index) { if (index 0 || index size) { return; } Node* prev dummy; while (index-- 0) { prev prev-next; } Node* toDelete prev-next; prev-next toDelete-next; delete toDelete; size--; } };代码看起来不多但每个函数背后都有几个值得反复琢磨的设计决策。接下来逐个拆。3.2 各成员函数核心逻辑拆解get函数的核心是先做区间判断然后从dummy-next出发走index步。这里有个小细节while (index-- 0)是先判断后自减所以当index 0时不会进入循环直接返回第一个节点的值刚好对应索引 0。这个写法比for (int i 0; i index; i)更紧凑但可读性稍差你自己写的时候按习惯来就行关键是别多走一步或者少走一步。addAtHead是五个操作里最“干净”的直接创建新节点然后让新节点的next指向原来的头节点再更新dummy-next。如果你用“头节点直接作为属性”的方案这里要单独处理链表为空的情况但有了dummy什么都不用判断。注意顺序不能反先node-next dummy-next再dummy-next node。如果顺序反了原来的头节点就丢了链表会断掉。addAtTail需要从头遍历到尾部再从尾部插入。这里有个优化的点如果频繁在尾部插入可以额外维护一个tail指针让addAtTail变成 O(1)。但为了保持代码简单我没有加因为addAtIndex本身就允许index size遍历法是统一路径。如果你追求极致性能可以考虑维护尾指针但注意在deleteAtIndex删除最后一个节点时要更新tail这就引入了新的边界条件自己权衡。addAtIndex是最难写对的核心方法。关键在于prev初始化为dummy然后循环走index步。为什么是index步因为我们要插入到“索引为 index 的节点之前”所以需要找到索引为index - 1的节点作为前驱也就是从dummy出发走index步dummy本身不算索引第一步走到索引 0第 index 步走到索引 index-1。比如在链表1 - 2 - 3中调用addAtIndex(1, 9)我们希望得到1 - 9 - 2 - 3新节点要插到索引 1 的位置也就是值为 2 的节点之前那么前驱是值为 1 的节点从dummy走 1 步刚好到达它。这一步要是没想明白整个addAtIndex一定写出错。deleteAtIndex的逻辑与addAtIndex类似也是让prev走index步走到目标节点的前驱然后执行“跳过并释放”。注意这里一定要把被删节点先保存到一个临时变量里再更新链接最后delete。如果你只写成prev-next prev-next-next;那被删节点的内存就泄漏了虽然 LeetCode 的判题器不一定会对你的内存泄漏报错但这在真实项目里就是事故。我见过太多人面试时写出不带delete的 C 链表删除然后面试官追问“这个节点内存去哪了”时直接愣住。3.3 时间复杂度与空间复杂度对照这题的复杂度分析也是面试必问项我整理成了表格方便你直接背操作时间复杂度说明get(index)O(n)最坏情况遍历 n 次addAtHead(val)O(1)借助 dummy无遍历addAtTail(val)O(n)需遍历到尾部可用 tail 指针优化为 O(1)addAtIndex(index, val)O(n)遍历到指定位置deleteAtIndex(index)O(n)遍历到指定位置空间复杂度是 O(n)n 是链表节点数。这里有个容易混淆的点虚拟头节点算不算空间复杂度严格说虚拟头节点只有一个属于常数空间所以空间复杂度依然是 O(n)不是 O(n1)。3.4 Python 版本快速留档如果你主要用 Python 刷题代码会短很多因为不用手动管理内存。Python 里的对象引用自带“垃圾回收”所以deleteAtIndex不需要也不能主动释放内存只管把引用断开就行。class Node: def __init__(self, val0, nextNone): self.val val self.next next class MyLinkedList: def __init__(self): self.dummy Node(0) self.size 0 def get(self, index: int) - int: if index 0 or index self.size: return -1 cur self.dummy.next for _ in range(index): cur cur.next return cur.val def addAtHead(self, val: int) - None: self.dummy.next Node(val, self.dummy.next) self.size 1 def addAtTail(self, val: int) - None: cur self.dummy while cur.next: cur cur.next cur.next Node(val) self.size 1 def addAtIndex(self, index: int, val: int) - None: if index self.size: return if index 0: index 0 prev self.dummy for _ in range(index): prev prev.next prev.next Node(val, prev.next) self.size 1 def deleteAtIndex(self, index: int) - None: if index 0 or index self.size: return prev self.dummy for _ in range(index): prev prev.next prev.next prev.next.next self.size - 1Python 版本有一个小细节Node(val, self.dummy.next)这种写法等价于先创建Node再赋值next我这一行就完成了。你要是第一次写建议先用多行形式思路更清晰后面熟悉了再压缩。4. 常见问题与调试排查实录4.1 我实际踩过的三个坑第一次提交 707 的时候我自认为逻辑完美结果连续三次提交都有用例过不了。复盘之后发现全是一些很“低级”但很典型的错误分享出来给你避坑。第一个坑只处理了插入和删除逻辑忘了更新size。有一次我在addAtIndex里加了size但在addAtHead里忘了加然后get的时候索引完全错乱链表明明有 5 个节点size却还是 4最后一个节点永远访问不到。这个问题的排查方法很简单写一个辅助函数打印size和链表所有元素跑几个用例马上就能看出账目对不上。第二个坑删除头节点时dummy的指向没更新。我用的是带dummy的实现按理说不会踩这个坑但有一次我改代码时不小心在deleteAtIndex里写成了if (index 0) { dummy dummy-next; delete dummy; }这等于把dummy本身给删了直接导致后续访问崩溃。正确的做法永远是通过prev找前驱再删除而不是动dummy本身。第三个坑addAtIndex中index size的情况没单独想清楚。当时我写的是先判断if (index size) return;然后让prev走index步。在index size的场景下prev会从dummy一直走到dummy-next nullptr的最后一个节点的前一个位置不对其实是走到最后一个节点本身。这里没法靠猜必须画图验证。4.2 画图 打印调试法链表调试最忌讳空想我强烈建议你准备纸笔或者用电脑上的画图工具把节点和指针一个个画出来。以deleteAtIndex(1)为例假设链表是dummy - 1 - 2 - 3你先标出谁是prev从dummy走 1 步到节点 1然后要删的是节点 2因此执行prev-next prev-next-next这时代码里的指针关系是1.next 3然后delete 2。画一遍图之后你会发现指针操作本质上就是“改箭头的指向”根本不用背代码。写代码的时候我建议在局部范围先写一个调试辅助函数void printList() { Node* cur dummy-next; while (cur ! nullptr) { cout cur-val - ; cur cur-next; } cout NULL, size size endl; }然后在每个操作函数的前后调用它看看链表形态是否符合预期。这比打断点更直观因为你看到的是一整条链的全貌而不是某个局部变量的值。4.3 常见报错与排查速查表我把常见的运行时报错和对应的排查方向整理成表你对照着检查会省很多时间症状可能原因排查方向编译报错member access into null pointer访问了空指针的val或next检查get和deleteAtIndex是否先做了合法性判断本地运行正常LeetCode 报堆缓冲区溢出越界访问节点内存重点检查while循环步数可能多走或少走一步插入后get返回错误值size未更新或index语义不清打印size和链表全貌确认索引从 0 开始删除后链表完全丢失删除头节点时误删dummy检查dummy本身是否被修改或释放C 版本多次提交后内存暴涨删除节点时没有delete搜索代码里所有new确认配对delete空链表调用get(0)返回 0初始化返回值写错确认get无效索引返回 -1而不是默认值还有一个很隐蔽的坑while (index-- 0)这个写法虽然简洁但如果你在循环体内部又对index做了修改那就乱了。所以循环里千万别动index它只是个“步数计数器”。我以前在图省事时把index--和prev prev-next写在一行结果逻辑混乱后来老老实实分开写一眼就能看清楚。5. 从 707 延伸到真实场景5.1 循环单链表、双向链表、链表逆序的扩展热词里出现了“循环单链表”“单循环链表”“逆置链表”“基于链表的两个集合的差集”这些内容都和 707 高度相关。如果你 707 写完还有余力建议把这三个变种都看看。循环单链表指的是尾节点的next不再指向nullptr而是指回头节点。它的好处是可以从任意节点出发遍历整个链表但坏处是遍历的终止条件变了不再是cur nullptr而是cur 起始节点。在 707 的代码基础上改造循环单链表很容易的一个玩法是把尾节点接到dummy上而不是nullptr然后addAtTail和addAtHead就变成了对称操作很有意思。双向链表就是在每个节点多加一个prev指针插入和删除时要同时维护两个方向的引用。热词里“c结构体链表基本语法”往往就要求你能同时定义单链和双链的结构体。我建议你在 707 之后手动写一遍双链表重点体会“先接后断”的原则插入新节点时先把新节点的next和prev都接好再断开旧链接这样能防止中间状态出现悬空指针。链表逆序逆置链表是另一类高频题。它的核心思想是三个指针prev、cur、next每次把cur-next指回prev然后三个指针整体后移。707 里你已经在addAtIndex和deleteAtIndex中反复练习了prev指针的移动再做逆序题时会容易很多。5.2 嵌入式 / 内核链路中的链表代码示例热词里“嵌入式链表代码示例”值得多说一句。在主流的嵌入式内核比如 Linux kernel、RT-Thread里链表与 707 里的“数据节点带next指针”有一个重要的结构差异它们用的是侵入式链表。所谓侵入式就是链表节点结构体list_head被嵌入到你自己的业务结构体里而不是让业务结构体“继承”链表的指针字段。用代码表示struct list_head { struct list_head *next, *prev; }; struct my_data { int value; struct list_head list; // 链表节点嵌入到业务结构体 };使用时通过list_entry/container_of宏从list_head的地址反推出整个my_data结构体的地址。这种设计的好处是一个链表节点可以同时挂到多个链表上比如同时挂到哈希表和 LRU 链表而且不强制数据的组织方式。你要是从 707 的直接指针实现切到侵入式链表刚开始会很不适应因为cur-next返回的不再是你的数据节点而是一个list_head你必须再用container_of才能拿到业务数据。但正是这种思路让 Linux 内核的链表操作无比灵活。707 题里练好的“前驱节点插入”“删除节点”这些基本功在侵入式链表里完全通用唯一要变的是指针类型的转换。所以我一直觉得刷好 707 这类基础题再去看内核链表的源码绝对事半功倍。5.3 刷题与面试建议关于 707 的刷法我自己的建议是至少写三遍第一遍用 Python先把逻辑理顺避免被内存管理干扰第二遍用 C重点练内存释放和指针操作第三遍给自己限时 15 分钟看看能不能一次写对、不靠调试。三遍下来链表的基本功基本就焊死了。面试中如果遇到这题面试官通常不只问“能不能跑通”还会追问几个延伸问题你的addAtIndex时间复杂度是多少为什么用虚拟头节点deleteAtIndex在 C 里怎么避免内存泄漏如果链表特别长get操作频繁怎么优化。这些问题我在前面的章节都覆盖到了你最好能把原因讲出来而不是只背答案。我个人体会是能把边界条件讲得清清楚楚的候选人比能闷头写完五道题的候选人更受欢迎因为这代表你真的理解了数据结构在做什么。回到这题本身LeetCode 707 刷完最大的价值不是会做这道题而是你真正建立起了一个“链表操作肌肉记忆”什么情况下需要前驱节点如何维护 size如何统一头尾插入。这些肌肉记忆会在你处理 LRU Cache、并查集、图论邻接表的时候反复被调用。我现在自己在写嵌入式代码里的链表时最常用的还是 707 里练出来的那套手法——先画图、再动指针、最后验证边界。希望你也能通过这题把链表彻底拿捏。