LeetCode 707 这道题官网难度标的是“中等”标签是“设计 链表”。每次有人问我力扣怎么入门、链表怎么练我都会先推荐这道题。原因特别简单它没有任何花哨的算法不涉及动态规划、不涉及贪心唯一考的就是你对链表这个最基础的数据结构到底理解到什么程度。把它写明白你的链表基本功就过关了一半。这道题要求你实现一个MyLinkedList类支持get、addAtHead、addAtTail、addAtIndex、deleteAtIndex五个操作。看起来只是实现一个简化版链表实际上在考你对虚拟头节点、边界条件、指针维护这三大难点的掌握。很多从数组起步的朋友第一次写链表就会栽在空节点、尾节点、越界这几个地方。这篇文章我会把两种主流实现都拆开讲透附上完整的 C 和 Python 代码再把常见的调试手法和坑点挨个列出来适合刚刷到链表专题的新手也适合想彻底搞懂链表设计的进阶读者。1. 题目整体设计与思路拆解1.1 题目到底在要求什么先别急着写代码把题目要求逐字读一遍。力扣 707 给出的MyLinkedList是一个单链表结构但所有操作都要自己实现包括get(index)获取链表中下标为index的节点值下标从 0 开始非法下标返回 -1。addAtHead(val)在链表头部插入一个值为val的节点。addAtTail(val)在链表尾部追加一个值为val的节点。addAtIndex(index, val)在下标为index的节点前插入新节点。如果index等于链表长度则插到尾部如果index大于链表长度则不插入。deleteAtIndex(index)删除下标为index的节点非法下标直接忽略。这里有一个容易忽略的细节addAtIndex里index size是合法的意味着你要能处理“插在最后一个节点后面”的情况。很多第一次写的人只把注意力放在“中间插入”上导致链表为空或者插尾部的时候程序直接崩溃。还有一点题目并没有要求实现size()方法但你自己的数据结构里必须维护一个size字段。这个字段决定了get和deleteAtIndex的合法性判断也是addAtIndex判断“等于长度时插尾部”的依据。不维护 size每次现算链表长度代码会啰嗦且容易出错。1.2 为什么一道“设计题”反而最练基本功你可能会想刷链表题直接刷反转链表、合并两个有序链表不香吗那些题虽然热门但本质上是在已有链表结构上做指针移动你只需要在某个局部处理几个next指向就算出错也很好定位。但 707 这类设计题不一样它逼你从零开始定义节点、管理链表生命周期、处理所有边界情况。这就像学开车。反转链表相当于练“侧方停车”是个专项动作而 707 相当于让你完整地跑一遍“上车、起步、变道、停车”的流程。没有完整流程的训练专项动作练得再熟真上了路也会手忙脚乱。在工程里绝大多数链表相关 bug 都出在“边界”而不是“核心逻辑”。空链表、只有一个节点、操作头节点、操作尾节点这四种情况几乎覆盖了 90% 的边界问题。707 恰好把这四种情况全部揉进了五个操作里做完这一道等于一次性把链表的所有边界情况摸了一遍。1.3 单链表还是双链表怎么选做题之前先做个方案决策用单链表实现还是双链表实现两种方案的差异主要集中在addAtTail和deleteAtIndex上。对比维度单链表双链表节点结构val nextprev val nextaddAtHeadO(1)O(1)addAtTailO(n)要遍历到尾部O(1)有尾指针getO(n)O(n)可从两端近端出发空间开销每个节点 1 个指针每个节点 2 个指针插入/删除时指针维护只需改 2 处 next要改 2 对共 4 处指针代码出错难度较低较高容易漏改 prev从面试角度看用双链表实现能展示你对结构的理解更深因为它能同时维护prev和next很多后续要刷的题目比如 LRU 缓存底层就是双链表。但从学习角度看我建议先写单链表把基础逻辑跑通后再改成双链表感受一下两者在指针维护上的差异。下面两节我会分别给出两种实现的完整代码和逐步讲解。2. 核心细节解析与实操要点2.1 虚拟头节点解决空链表边界的利器写链表代码时最怕什么最怕操作的是空链表或者头节点。比如addAtHead如果你手头只有head指针空链表时head nullptr插入后要单独判断并更新head非空链表时又要把head指向新节点。每个方法都要写一遍这种判断代码不优雅还容易漏。更好的做法是引入一个虚拟头节点也叫哨兵节点。它在真正的头节点之前永远存在不存储有效数据只是为了让“空链表”和“非空链表”在代码层面变成同一种形态。你可以把它想象成火车站站台上的安全线。站台上画一条线不管有没有火车你都站在线后面虚拟头节点就是这条线有节点没节点操作逻辑都是统一的。实际代码里用dummyHead表示这个节点真正的链表数据从dummyHead-next开始。空链表时dummyHead-next nullptr非空时指向第一个有效节点。这样一来addAtHead和普通的“当前节点后插入”就变成同一个操作不需要任何条件分支。我见过不少选手在刷题时不用虚拟头节点也能把 707 写对但代码里充满了if (head nullptr)之类的分支调试起来要反复确认当前状态。用虚拟头节点是工程上的最佳实践后面做 21 题合并两个有序链表、206 题反转链表时会发现它同样好用。2.2 五个方法的逐个拆解含边界条件这里不急着贴代码先把每个方法背后的逻辑和要防的坑说清楚。get(index)从dummyHead出发先做合法性校验判断index是否在[0, size)区间内。然后让一个cur指针指向dummyHead-next循环index次每次向后移动一个节点。这里有个小技巧循环条件是while (index--)如果index等于 0循环一次都不执行直接返回第一个节点的值语义非常清晰。addAtHead(val)创建一个新节点让它的next指向dummyHead-next再把dummyHead-next更新为新节点。这里的关键是更新顺序不可颠倒如果先改dummyHead-next原来的头节点就找不到了新节点就接不上链。最后别忘了size。addAtTail(val)从dummyHead开始不断cur cur-next直到cur-next nullptr这个cur就是当前的尾节点让cur-next new node即可。写单链表时这个方法必然是 O(n) 的想优化就只能改成双链表或维护尾指针。addAtIndex(index, val)这是最复杂的一个方法。先看index是否合法合法区间是[0, size]注意右边界是闭区间因为index size表示插在尾部。然后用一个cur从dummyHead出发向前走index步走完后cur恰好是插入位置的前驱节点。接着执行“新节点先连后再断旧链”的操作最后size。deleteAtIndex(index)先判断index是否在[0, size)内。然后找到被删节点的前驱让前驱的next跳过被删节点指向被删节点的后继。如果是 C还要记得delete掉被删节点避免内存泄漏。2.3 几个容易踩的坑size、断链、空指针第一个坑是不维护size。有的同学图省事每次get或者addAtIndex都现场数链表长度这样写不仅慢而且容易在“空链表特殊逻辑”里绕晕。维护一个int size每次插入加一、删除减一所有合法性判断都基于它是最稳的做法。第二个坑是指针更新顺序错了导致链表断链。插入操作的标准顺序是新节点先指向后继再把前驱指向新节点。以addAtHead为例newNode-next dummyHead-next; dummyHead-next newNode;如果顺序颠倒先把dummyHead-next改成newNode原来的头节点就永远找不到了后面的链全丢了。这属于低级但高发的错误尤其紧张的时候容易犯。第三个坑是忘了处理空指针。比较典型的是手写双链表删除时没有判断prev或next是否为nullptr直接对空指针解引用运行时直接报错。链表题目里的空指针错误几乎都出在边界节点上比如删头节点、删尾节点、对空链表操作。代码里一旦出现p-next-next这种连写就要条件反射地检查p-next是否可能为空。更稳妥的做法是统一用虚拟头节点和虚拟尾节点双链表场景从根上避免空指针判断。3. 实操过程与核心环节实现3.1 C 单链表实现完整代码 逐段讲解下面给出一版可以直接提交的 C 单链表实现我加了注释重点看每个方法的指针操作顺序和边界判断。class MyLinkedList { private: struct Node { int val; Node* next; Node(int x) : val(x), next(nullptr) {} }; Node* dummyHead; int size; public: MyLinkedList() { dummyHead new Node(0); size 0; } int get(int index) { if (index 0 || index size) return -1; Node* cur dummyHead-next; while (index--) { cur cur-next; } return cur-val; } void addAtHead(int val) { Node* newNode new Node(val); newNode-next dummyHead-next; dummyHead-next newNode; size; } void addAtTail(int val) { Node* cur dummyHead; while (cur-next ! nullptr) { cur cur-next; } cur-next new Node(val); size; } void addAtIndex(int index, int val) { if (index 0 || index size) return; Node* cur dummyHead; while (index--) { cur cur-next; } Node* newNode new Node(val); newNode-next cur-next; cur-next newNode; size; } void deleteAtIndex(int index) { if (index 0 || index size) return; Node* cur dummyHead; while (index--) { cur cur-next; } Node* toDelete cur-next; cur-next cur-next-next; delete toDelete; size--; } };逐段拆解一下。MyLinkedList构造函数里只做两件事创建虚拟头节点、把size初始化为 0。注意虚拟头节点的val随便给个 0 就行它永远不会被读取。get方法的循环次数需要仔细理解。index是“从第一个有效节点开始往后数几个节点”的意思所以让cur从第一个有效节点出发跑index步就能到目标节点。很多人在这里写成for (int i 0; i index; i)效果是一样的但我个人更喜欢while (index--)这种写法简单直接还能避免在循环里误改原值——这里本来也不需要保留原来的index。addAtIndex里的步数要从dummyHead开始算。因为要在下标index的节点前面插入所以cur应该停在“下标 index 节点的前驱”也就是dummyHead走index步。比如index 0走 0 步cur就是dummyHead新节点直接插在虚拟头后面正好成为第一个有效节点。比如index size走size步后cur是最后一个有效节点新节点插在它后面正好是尾部。这个设计非常优雅边界情况不需要额外判断。deleteAtIndex同理cur停在被删除节点的前驱。当index 0时cur是dummyHead成功删除第一个有效节点这就是虚拟头节点的好处。提示C 里如果你用new创建了节点即使在力扣的判题环境里不delete也能通过但工程习惯上还是要删除避免内存泄漏。上面代码里deleteAtIndex是完整的写法建议学这个习惯。单链表实现的复杂度非常清晰addAtHead是 O(1)addAtTail是 O(n)get、addAtIndex、deleteAtIndex都是 O(n)因为都要遍历链表找位置。整体空间复杂度 O(n)。3.2 双链表实现空间换时间的典型单链表写顺之后可以再写一遍双链表。双链表每个节点多一个prev指针插入和删除时要维护的指针数量翻倍但换来的是addAtTailO(1) 的收益。我的做法是同时维护虚拟头节点head和虚拟尾节点tail。链表有效数据夹在head-next和tail-prev之间。这样做的好处是addAtTail不需要遍历直接在tail之前插入删除最后一个节点也不会遇到nullptr。class MyLinkedList { private: struct Node { int val; Node* prev; Node* next; Node(int x) : val(x), prev(nullptr), next(nullptr) {} }; Node* head; Node* tail; int size; public: MyLinkedList() { head new Node(0); tail new Node(0); head-next tail; tail-prev head; size 0; } int get(int index) { if (index 0 || index size) return -1; Node* cur head-next; while (index--) cur cur-next; return cur-val; } void addAtHead(int val) { Node* newNode new Node(val); newNode-prev head; newNode-next head-next; head-next-prev newNode; head-next newNode; size; } void addAtTail(int val) { Node* newNode new Node(val); newNode-prev tail-prev; newNode-next tail; tail-prev-next newNode; tail-prev newNode; size; } void addAtIndex(int index, int val) { if (index 0 || index size) return; if (index 0) { addAtHead(val); return; } if (index size) { addAtTail(val); return; } // 找到当前下标 index 的节点新节点插在它前面 Node* cur head-next; while (index--) cur cur-next; Node* newNode new Node(val); newNode-next cur; newNode-prev cur-prev; cur-prev-next newNode; cur-prev newNode; size; } void deleteAtIndex(int index) { if (index 0 || index size) return; Node* del head-next; while (index--) del del-next; del-prev-next del-next; del-next-prev del-prev; delete del; size--; } };双链表的deleteAtIndex我写得更简洁直接让del走到目标节点然后用del-prev和del-next四行代码把前后连接重新搭好再删掉del。维护双链表时最容易犯的错误是只改了prev或者只改了next导致链表从中间断开。我的经验是每次写完插入或删除立刻在心里过一遍“从 head 走到 tail再从 tail 走回 head两趟都能走通吗”如果两趟都通大概率代码没问题。双链表版本里addAtTail是 O(1)其他方法依然是 O(n)。这个“其他方法 O(n)”是由链表结构决定的只要还需要通过下标找节点就必须遍历。想真正 O(1) 访问下标就得用数组了那就变成另一道题了。3.3 Python 实现与不同语言间的差异Python 刷题也很常见这里给一版简洁的 Python 单链表实现。Python 没有指针语法也不需要手动delete节点把引用断开即可GC 会自动回收不可达的对象。class Node: def __init__(self, val): self.val val self.next None 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: node Node(val) node.next self.dummy.next self.dummy.next node 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 0 or index self.size: return cur self.dummy for _ in range(index): cur cur.next node Node(val) node.next cur.next cur.next node self.size 1 def deleteAtIndex(self, index: int) - None: if index 0 or index self.size: return cur self.dummy for _ in range(index): cur cur.next cur.next cur.next.next self.size - 1用 Python 写链表有一个容易被忽略的坑Python 的Node对象本质是引用。你写cur cur.next是在移动引用不会改链表结构但如果你写cur.next cur.next.next就是在修改链表了。刷题时很多人把引用赋值和结构修改搞混多写几遍就会形成条件反射。C、Python、Java 三个语言实现 707 最大的差异在内存管理上。C 要手动new和deleteJava 和 Python 都靠 GC 自动处理。面试时如果选 C面试官可能会追问内存泄漏、悬垂指针的问题选 Java 或 Python 则会追问“为什么不需要手动释放”。建议至少用两种语言各写一遍理解会更深。4. 常见问题与排查技巧实录4.1 高频 Bug 速查表这道题提交时常见的报错就那么几类我用一个表格把现象、原因和解决办法整理出来刷题时可以直接对照。报错现象原因解决办法执行get(0)返回 -1但明明插入过节点构造函数或插入后忘了维护size检查所有插入操作是否都执行了size删除是否执行了size--addAtHead后链表丢失了原来的第一个节点插入时先改了dummyHead-next导致原头节点无法访问严格按照“新节点先指向后继前驱再指向新节点”的顺序addAtIndex(0, val)插入失败或插错位置遍历时把cur初始为dummyHead-next而不是dummyHeadaddAtIndex要从虚拟头出发走 index 步让cur停在插入位置的前驱空链表上调get(0)崩溃没有判断index size直接对nullptr解引用入口处统一做下标合法性校验双链表删除后双向遍历到一半断掉只改了prev或只改了next没有成对更新写完代码后手动走一遍双向路径检查C 提交出现内存错误但逻辑看起来没问题删除时没有delete节点或dummyHead没初始化检查构造函数是否初始化了虚拟头节点和 size上面这些 bug 我自己都犯过尤其是“先改前驱再改新节点”的顺序第一次写时极容易错。这里有一个百试百灵的小技巧插入操作统一记成“先定新节点的左右邻居再回头改左右邻居的指针”。新节点的两个指针先赋值再改旧节点的指针旧节点指针要么只有一个单链表要么有两个双链表永远在最后处理。4.2 调试技巧如何用最简单的手段定位问题力扣的调试环境比本地 IDE 弱一些遇到复杂 bug 时我习惯在本地写一个测试框架把每一步操作后的链表完整打印出来。这个习惯帮我省下了大量时间。核心是一个printList函数可以把当前链表从头到尾打印一遍。比如 C 里可以写void printList() { Node* cur dummyHead-next; while (cur ! nullptr) { std::cout cur-val - ; cur cur-next; } std::cout nullptr std::endl; }然后在每一步操作后调用它格式类似MyLinkedList list; list.addAtHead(1); list.printList(); // 1 - nullptr list.addAtTail(3); list.printList(); // 1 - 3 - nullptr list.addAtIndex(1, 2); list.printList(); // 1 - 2 - 3 - nullptr list.deleteAtIndex(1); list.printList(); // 1 - 3 - nullptr如果实际输出和预期不一致立刻就知道是插入位置错了还是删除指向错了。对于双链表还可以加一个反向打印函数从tail-prev往前遍历验证prev指针是否维护正确。还有一种很有效的调试方法是“画图推演”。链表题最怕脑子跟着代码绕画不出来就理不清。我的习惯是在纸上画出当前链表结构用方框表示节点用箭头表示next和prev一步步在图上执行代码逻辑。很多指针顺序错误在纸上一眼就能看出来。4.3 提交不过怎么办从超时到越界的排查路径如果你提交后报的时间超限TLE大概率不是算法复杂度问题而是代码里出现了死循环。链表死循环的典型写法是遍历时用错了循环条件比如把while (cur-next ! nullptr)写成while (cur ! nullptr)然后循环体里又移动了cur结果访问到空指针后不再移动在原地打转。遇到 TLE先在本地用超长用例测试或者加上计数器判断是否循环超过链表长度的次数能快速定位死循环位置。如果你提交后报的越界访问AddressSanitizer 报 heap-buffer-overflow通常是访问了链表之外的空指针。我的排查顺序是先检查所有方法开头的合法性判断是否齐全尤其是get和deleteAtIndex。再看addAtIndex是否遗漏index size的分支。最后检查 C 代码里是否出现了cur-next-next这种连写而cur-next恰好为nullptr。大部分越界错误都能在前两步找到。如果前两步都没问题就在关键访问点前加打印把index和size打出来马上能看到是谁越界。5. 这道题做完之后的延伸方向707 是一道“地基型”题目它的价值在于把你对链表的理解从“好像懂了”推向“真的会写”。打完地基之后我建议立刻去刷几道直接复刻链表操作的题效果会非常明显。第一道是 206 反转链表。反转链表的核心就是反复执行“摘下一个节点插到虚拟头的后面”本质上和你今天写的addAtHead一模一样。707 里把addAtHead写熟了反转链表就只剩三行核心代码了。第二道是 21 合并两个有序链表。这道题也建议用虚拟头节点实现你只需要维护一个tail指针反复比较两个链表的头节点把小的挂到tail后面逻辑和addAtTail高度重合。做完 707 再写 21速度会有肉眼可见的提升。第三道是 146 LRU 缓存。这道题不强求新手立刻去碰但当你熟练双链表版本后可以回来看一眼。LRU 的经典实现就是哈希表加双链表你要自己维护插入、删除、移动三个操作每步都跟 707 的双链表实现息息相关。我个人在实际刷题中的体会是基础题的价值不在于“难住你”而在于“重复你”。707 的五个方法本质上是同一种操作换了几个入口在指定位置前插入、在头部插入、在尾部插入。你把这些操作在多道题里反复重复手指会自动形成记忆写链表代码就会从“仔细想”变成“条件反射”。最后再分享一个小技巧刷 707 时一定要在本地写一个完整的测试脚本把官方样例跑完再自己补几个边界用例比如空链表上get(0)、在最大合法下标处插入、删除最后一个节点、连续多次addAtHead等。不用跑大用例只要这些边界用例全过提交基本就一次过了。链表题的边界就那么几个提前主动踩一遍比在提交页一个个试要省心得多。