力扣707“设计链表”在力扣热题100里算是一个不算难、但特别磨人的基础题。题目本身很直白让你手写一个单链表实现get、addAtHead、addAtTail、addAtIndex、deleteAtIndex五个方法。很多朋友第一次提交就开始怀疑人生代码看着就几十行怎么编译不过怎么几个边界条件全挂我把这题列为“链表基本功”的第一道必刷题因为它把链表遍历、链表插入、删除节点、索引合法性检查这些最核心的操作浓缩在一个类里堪称单链表基本操作的最小实验场。我当时刷这题最大的感受是会写链表的人不是背会了某个模板而是脑子里有清晰的“图”。你看着代码很简单但一旦走到index边界、头部插入、删除最后一个节点这些场景没有图示全靠硬推十有八九会翻车。这篇博客会把707从头到尾拆开聊清楚为什么虚拟头节点是省事神器、五个操作的边界条件到底怎么定再给一份完整可跑的C实现和调试技巧。适合刚开始刷链表题的读者也适合打算用这道题复习数据结构基础的人。1. 题目拆解设计链表到底在考什么1.1 这道题要求你实现什么力扣707“设计链表”原题要求实现一个MyLinkedList类支持五个操作get(index)获取链表中第index个节点的值如果索引无效则返回-1。addAtHead(val)在链表第一个元素之前插入一个值为val的节点。addAtTail(val)将值为val的节点追加到链表末尾。addAtIndex(index, val)在链表中的第index个节点之前插入值为val的节点。如果index等于链表长度则插入到末尾如果index大于链表长度则不插入如果index小于0则在头部插入。deleteAtIndex(index)删除链表中第index个节点如果index无效则不操作。很多人第一眼看过去觉得不过如此但实际一写就会发现坑很多。比如addAtIndex这个操作允许index等于size不允许index大于sizeindex是负数时又要变成头插这跟get和delete的边界完全不同。题目没有直接给你一套统一的规则而是让你自己把每个操作都讲清楚、写清楚所以它考的不是你会不会用std::list而是你有没有真正理解链表这种结构的指针操作。1.2 这道题为什么值得刷力扣热题100里链表专题的题目并不少但707是所有题目的地基。你可以去刷合并两个有序链表、反转链表、删除倒数第N个节点、环形链表这些题表面上是各种花哨操作本质上都在反复使用三件事遍历链表、在某节点后插入、删除某节点的后继。707把这三种能力压缩成了一道题而且不允许你偷懒调用现成容器必须自己从零实现一个类。另一个重要原因是面试压力场景下手写链表是最容易暴露代码习惯的题。我见过不少候选人解题思路说得很好一写到addAtIndex边界条件就乱套要么忘了如何处理index为负数要么在index等于size时把追加操作漏掉要么在插入操作里先把prev-next改了导致后面的节点丢了。707就是专门用来治这种毛病的题。刷透它后面再碰链表题你会明显觉得那些花哨技巧都有套路可循。还有一点很实惠这道题覆盖了C内存管理的基础操作。new出来的节点删除时要记得delete析构时要把整条链清干净。很多刷题用Python或JavaScript的朋友可能没这个困扰但用C刷这题正好补齐了内存手动管理的经验。1.3 单链表和双链表的取舍707的官方写法默认是单链表这已经足够应对全部测试用例。不过热词里总有人提“php双链表”“c双链表”之类的再实现版本。我去研究过双链表写法确实可行每个节点多一个prev指针get操作也可以从头部走或者从尾部走某些情况下能优化一半遍历时间。但代价也很实在代码量几乎翻倍插入和删除时要同时维护两个方向的指针稍不留神就会把prev和next搞乱。我的建议是第一遍老老实实用单链表做707把基础逻辑跑通之后再尝试用双链表重写一遍。双链表版本能加深你对指针连接顺序的理解尤其是处理prev指针时你会发现“先改新节点的前后指针再改相邻节点的指向”这套顺序不能乱。但如果你现在还在刷题初期别一上来就挑战双链表容易在调试指针时把自己绕晕。2. 核心设计虚拟头节点为什么是神2.1 没有虚拟头节点的一天先说说一个很多新手没意识到的痛点如果没有虚拟头节点头插和删除头节点要单独写一套逻辑。比如addAtHead时你要把新节点的next指向原来的head然后更新headdeleteAtIndex删除第一个节点时你要让head指向head-next。这意味着你的代码里会有很多类似于“if (index 0) { head ... } else { ... }”的特判写着写着就会漏掉一种情况。虚拟头节点的思路很简单在真正的第一个节点前面永远挂着一个不参与计数的“哨兵节点”。它不存业务数据只在链表头部占个位置。这样一来所有插入和删除操作都统一成“在某个节点的后面插入一个新节点”或“删除某个节点后面的节点”。头部插入就变成了在虚拟头节点后面插入删除头部节点就变成了删除虚拟头节点后面的节点。整个类的代码逻辑因此变得非常干净不需要为头节点做任何特殊处理。我在实际写代码时会把这个虚拟头节点命名为dummy并在注释里写清楚“dummy-next才是真正的链表头”。这个命名习惯帮我少踩了很多坑。面试时如果考官问为什么要加虚拟头节点你就直接说为了消除头节点的边界特判让五个操作共用同一套指针逻辑。2.2 搞清楚索引规则边界条件不再发怵这道题最容易出错的地方就是索引规则的记忆。我发现把链表画在纸上能解决一大半问题。假设有一个长度为3的链表节点分别是A、B、C前面再挂一个虚拟头节点dummy。这时候dummy的位置可以理解为-1。A的位置是0。B的位置是1。C的位置是2。链表的末尾“空位”是3。get(index)要求index在0到2之间也就是[0, size-1]addAtIndex要求index小于等于3也就是[0, size]index小于0时要特殊处理成头插deleteAtIndex要求index在[0, size-1]范围内。这三套规则只要画一次图就能记得很牢。我自己的经验是每次写这道题前先手动画一遍链表图把dummy、各节点、末尾空位都标出来然后再写代码。画图花30秒但能避免在调试上花半小时。链表题的本质是“指针的重新指向”图比代码更接近真实运行状态。2.3 复杂度和空间开销先心里有数单链表版本的时间复杂度其实很好估算get需要从头部向后走index步最坏O(n)。addAtHead只需要改两个指针O(1)。addAtTail需要一路遍历到末尾再插入最坏O(n)。addAtIndex需要走到index位置最坏O(n)。deleteAtIndex需要找到待删节点的前驱最坏O(n)。空间复杂度方面每个节点是一个ListNode除了val就是next指针整体O(n)。如果你维护size变量还要额外一个整数但那是常数级不算什么。记住这些复杂度写代码之前就能判断自己的做法是否合格比如addAtHead如果写成遍历再插入明显是没理解头插的精髓。3. 五个操作逐项实现从定义到完整代码3.1 先搭好类的基本骨架用C写的话我习惯先定义ListNode结构体再写MyLinkedList类。完整骨架如下struct ListNode { int val; ListNode* next; ListNode(int v) : val(v), next(nullptr) {} }; class MyLinkedList { 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) { ListNode* node new ListNode(val); node-next dummy-next; dummy-next node; size; } void addAtTail(int val) { ListNode* node new ListNode(val); ListNode* cur dummy; while (cur-next) { cur cur-next; } cur-next node; size; } void addAtIndex(int index, int val) { if (index size) { return; } if (index 0) { index 0; } 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* toDelete prev-next; prev-next prev-next-next; delete toDelete; size--; } ~MyLinkedList() { while (dummy-next) { ListNode* tmp dummy-next; dummy-next dummy-next-next; delete tmp; } delete dummy; } private: ListNode* dummy; int size; };这段代码我实际测过能稳定通过力扣707的测试用例。类里维护了一个size变量理由是addAtTail和addAtIndex都需要判断链表长度如果每次都要遍历算长度addAtTail的过程会退化得很难看。有了sizeget和delete的合法性判断就是两次整数比较代价几乎为零。3.2 理解get的精髓走n步到达第n个节点get(index)的写法很多人第一反应是for循环我在这里用的是while (index--)。原因是它天然地把“从dummy-next出发走index步”这个动作表达得更直接。举个例子index2时cur先指向第一个节点然后index变成1继续移动到第二个节点再变0再到第三个节点。while结束时cur正好是第2个节点0-based。这个方法的重点是索引越界判断必须放在最前面否则cur会一路走到nullptr然后崩掉。还有一个细节当index0时while循环一次都不走cur就是dummy-next即第一个节点。这种行为跟预期完全一致。我发现很多人在这道题上犯错不是循环写错而是循环之前少了一句“if (index 0) return -1”导致index是-1时while条件永远为真cur直接越界。所以把边界检查放在函数开头是我写这道题时雷打不动的习惯。3.3 addAtTail为什么不能漏掉“先走到底”addAtTail从逻辑上看很简单就是走到最后一个节点然后接上新节点。但这个操作有个隐藏陷阱如果链表为空也就是dummy-next是nullptr那么从dummy开始循环while (cur-next)一次都不会走cur还是dummy然后cur-next node相当于完成了头插。这同样归功于虚拟头节点代码不需要单独判断链表是否为空。我在写addAtTail时喜欢用一个额外的指针cur而不是直接操作dummy。原因很简单dummy是类的成员遍历过程中不能让它溜走否则下一次addAtHead就找不到头了。另外size别忘了写很多人写完addAtTail一测试get(0)返回-1查半天发现size没更新。3.4 addAtIndex是整道题的分水岭addAtIndex的边界条件最复杂但掌握了“index等于size允许大于size不允许”这个规则后代码其实很统一。很多刚刷题的朋友会问为什么不写成if (index 0 || index size) return因为题目要求很明确index小于0时在头部插入而不是不操作。所以这个方法的正确姿势是如果index size直接return。如果index 0把index改成0等价于头插。接着是找插入位置的核心逻辑。插入在“第index个节点之前”那我们需要找到“第index-1个节点”作为prev。因为从dummy出发走0步到dummy走1步到第0个节点走index步正好到第index-1个节点。所以while (index--)会让prev停在正确的前驱节点上。这个过程我每次写都会在纸上推一遍因为一旦把index记成“走index1步”边界就全乱了。最后插入的两行要按固定顺序来node-next prev-next; prev-next node;这两行顺序不能反过来。如果先执行prev-next nodenode就接管了prev-next但是node-next如果还没指向原来的后继原来那段链表就彻底丢了。很多新手的链表插入错误都是从这里开始的。我把这两行的顺序总结成一句口诀先连后节点再改前节点。3.5 deleteAtIndex的两条铁律deleteAtIndex的边界检查和get一样index小于0或大于等于size时直接return。删除的时候同样是利用dummy来统一逻辑找到prev之后先保存要删除的节点toDelete再把prev-next指向prev-next-next最后delete toDeletesize--。这里最容易被忽略的有两个点。第一用C时必须delete掉被删节点否则就是内存泄漏。虽然力扣的判题一般不检查内存泄漏但作为训练养成new和delete配对的习惯很重要。第二保存toDelete这个临时变量不能省因为一旦执行了prev-next prev-next-next原来节点的地址就没人记住了后面想delete也找不到。我在第一次写这题时就吃过这个亏当时只改了指针没delete后来用Valgrind检查才意识到问题。3.6 五个操作的复杂度一图流方法平均时间复杂度空间复杂度关键边界条件get(index)O(n)O(1)index越界返回-1addAtHead(val)O(1)O(1)直接改dummy-nextaddAtTail(val)O(n)O(1)空链表时变成头插addAtIndex(index, val)O(n)O(1)indexsize不操作index0改为0deleteAtIndex(index)O(n)O(1)index越界不操作链表遍历是这里的共同底层操作get、addAtTail、addAtIndex、deleteAtIndex都依赖它。如果能做到“图在心中”看到任何一个操作都能立刻说出它要遍历几条指针那707的核心就吃透了。4. 常见问题与调试技巧实录4.1 边界条件为什么总写错我见过的最高频错误就是把addAtIndex的边界条件跟get搞混。get的合法区间是[0, size-1]addAtIndex的合法区间是[0, size]deleteAtIndex的合法区间是[0, size-1]。三者并不完全一样。如果你把这几个区间统一记成“index必须在[0, size-1]”那么addAtIndex在index等于size时追加到末尾的情况就会被漏掉。另一个高发错误是忘记处理index小于0。原题明确规定addAtIndex在index为负时执行头插可很多人拿到题之后想当然地认为负索引非法直接return。这个坑在样例里不一定测到但力扣的隐藏用例里有一提交就红。我自己的解决办法是把三类操作画成一张表贴在代码旁边操作合法区间特殊说明get[0, size-1]越界返回-1addAtIndex[0, size]小于0改成0大于size不操作deleteAtIndex[0, size-1]越界不操作边界条件这种问题靠记是记不住的靠画图和总结才能稳定不犯错。4.2 内存管理容易翻车的地方用C刷力扣时很多人会把addAtHead写成这样ListNode node(val); node.next dummy-next; dummy-next node;这是大忌。node是局部变量函数一结束栈上的空间就被回收了dummy-next指向的是一块无效内存。后面get的时候再去访问它行为完全不确定可能崩溃也可能读到垃圾值。正确写法必须用new在堆上创建节点让它的生命周期超过函数调用。delete方面也有一个常见误区删除节点后忘了把size减一。这个问题不会让程序立刻崩溃但会让get和delete的边界判断全部错乱。我自己调试时会在每个方法结尾检查size是否符合预期等于给代码加了一层显式状态校验。如果类里没写析构函数等到整个MyLinkedList对象销毁时链上的节点就全部泄漏了。这在本地开发中可能被内存检测工具抓出来在面试中也可能被追问。我在上面的完整代码里写了析构函数逐个delete节点。这套清理逻辑配合dummy可以保证整条链被彻底释放。4.3 用一个简单方法快速调试链表链表调试比数组调试麻烦因为你看不到“当前状态”。我在写707时习惯加一个辅助函数把链表内容打印出来void printList() { ListNode* cur dummy-next; if (cur nullptr) { cout empty endl; return; } while (cur) { cout cur-val ; cur cur-next; } cout endl; }每执行一个操作后打印一次链表内容再打印size很快就能定位是哪一步把链搞断的。比如连续addAtHead(1)、addAtHead(2)、addAtIndex(1, 3)然后get(0)不出结果这时打印链表会发现顺序是2 3 1说明addAtIndex的插入位置正确问题可能在get的索引计数。这种“操作后打印”的思路比断点调试更适合链表题因为你最关心的是指针之间的连接关系而不是某一行代码的具体值。4.4 刷完707之后还能怎么进阶707本身是单链表的“最小单位”刷完之后我强烈建议马上接着刷这几道它们都是力扣热题100链表专题里的常客21题“合并两个有序的单链表”需要你熟练遍历两条链并且不断选择较小节点接在后面跟addAtTail的原理很像。206题“反转链表”考察的是反复修改next指针的顺序和addAtIndex中的插入顺序有异曲同工之妙。19题“删除链表的倒数第N个节点”核心是快慢指针但删除部分的指针交接跟deleteAtIndex完全一致。142题“环形链表 II”重点在快慢指针的数学推导但你对链表遍历的流畅度决定推得顺不顺。如果你精力充足还可以用“c语言链表”或“c结构体链表基本语法”的思路把707重新写一遍刻意不用类的成员函数全部改成函数指针或裸指针形式。那样写一遍下来你会对链表结构的底层理解提升一个台阶。我见过有人用php刷这道题也见过用“单链表的基本操作实验”的方式在本地跑通全部用例这些都说明707作为基本功题目跨语言、跨场景的普适性很强。洛谷的B3631“单向链表”本质上也是这种模拟题用链表结构维护一个动态序列。这类题刷多了你会发现“设计链表”其实是在为后续一切链表操作打底。我个人在实际写这道题时的最大体会是不要急着写代码先在草稿纸上把dummy和各个节点画出来把prev、cur、node的位置全部标清楚再动键盘。很多边界错误不是因为你笨而是因为你跳过了画图这一步。画图能让你直观看到“indexsize时prev会停在哪个节点”也能让你明白为什么addAtIndex里要先把node-next接到prev-next上。这个习惯帮我搞定了后续大量链表题包括反转、合并、删除、环检测几乎不再犯指针顺序错误。再分享一个小技巧写完707之后把addAtIndex、deleteAtIndex这两个方法的逻辑背下来不是背代码而是背两条规则——“插入前先把新节点的next指向后继再把前驱的next指向新节点删除前先保存被删节点再让前驱跳过它”。这两条规则可以用在任何链表题里比任何模板都可靠。希望这篇博客能帮你在力扣707上少走弯路也愿你后面刷链表题时每一步都走得稳、看得清。