LeetCode 707 这道设计链表题在热门 100 题里属于那种看着简单、做起来全是细节的类型。题面要求你实现一个 MyLinkedList 类支持 get、addAtHead、addAtTail、addAtIndex、deleteAtIndex 五个方法本质就是让你徒手把单链表的核心操作完整写出来。不少刷题的人一开始都不太重视它觉得链表嘛数据结构课早学过了。可真到笔试现场或者面试手撕代码的时候越界判断、空链表插入、插入顺序写反、指针悬空这些问题一个接一个蹦出来写出来的代码漏洞百出。这篇文章我想把这道题彻底拆一遍。先讲题目真正在考什么再解释为什么我强烈建议用虚拟头节点、为什么必须维护 size然后五个方法逐一带着细节手写最后给出一份边界条件自查清单和 C、Python、Java 三个版本的完整参考实现。无论你是刚接触链表的新手还是准备面试想把手写链表练成肌肉记忆的老手这篇应该都能帮你省下不少反复试错的时间。1. 题目考点拆解一场关于细节的连环测试1.1 五个方法对应链表的全部核心操作先看题面到底要求什么。你需要实现一个类构造函数初始化一个空链表然后五个方法分别是get(index) 返回链表中第 index 个节点的值索引无效返回 -1addAtHead(val) 在头部插入一个节点addAtTail(val) 在尾部追加一个节点addAtIndex(index, val) 在第 index 个节点之前插入新节点如果 index 等于链表长度就追加到尾部大于长度则忽略deleteAtIndex(index) 删除第 index 个节点索引无效则忽略。注意这里 index 的语义0 表示头节点size-1 表示尾节点size 表示尾部之后的位置。addAtIndex 的边界规则和其他方法不同它是index 等于长度时合法而 get 和 deleteAtIndex 是index 等于长度时非法。就这一个区别就能让粗心的人栽跟头。这五个方法恰好覆盖了单链表最核心的一整套操作按索引查找、头插、尾插、指定位置插入、指定位置删除。也就是说只要把这道题吃透单链表的基础操作你基本上就全摸过一遍了后面再刷反转链表、合并有序链表、环形链表这些题都会轻松不少。1.2 表面考链表实际考的是边界条件很多人觉得这道题简单是因为他们只看到了链表操作这四个字却没意识到这道题真正想考察的是边界条件处理能力。单链表的算法本身并不复杂无非是遍历和改指针但遍历到哪一步停止什么时候允许操作什么时候直接返回这些判断才是决定代码能不能跑通的关键。具体来说题目考察的是这几件事第一节点模型能不能建对Node 里要有值字段和 next 指针/引用第二引用语义清不清晰你得明白 cur-next xxx 到底改的是谁、会不会把原有链表弄丢第三五个方法各自的合法索引范围能不能分清楚第四C 里有没有内存泄漏意识删节点之后知不知道要释放。这四件事叠在一起代码量虽然不大信息密度却非常高面试官完全可以通过这一道题判断出你对链表是真懂还是假懂。1.3 这道题适合谁来写如果你刚开始刷题建议把这道题当作链表入门的必修课来做不要跳过。很多教程让你直接背反转链表可反转链表里涉及的前驱、当前、后继三指针操作如果基础不牢很容易背了又忘。707 这道题的优势在于它不要求你发明任何技巧只需要老老实实把最基本的东西写对非常适合用来建立正确的链表心智模型。如果你已经在准备面试我同样建议在面试前重新手写一遍这道题。写链表代码很像运动员做基础动作一段时间不练就容易手生。我自己的习惯是每次准备面试都会先默写一遍 707写到 bug-free 再开始复习其他题目等于给自己一个手上没生的确认信号。2. 方案选型虚拟头节点与 size 字段缺一不可2.1 不带头节点的写法为什么容易翻车先讨论一个实现层面绕不开的选择要不要引入虚拟头节点dummy head。有经验的读者应该知道单链表很多时候会带一个不存储有效数据的头节点让所有操作的逻辑统一。但不少新手习惯直接用一个 head 指针指向真实节点这种写法会导致一个问题头节点的特殊性。举个例子如果不带头节点addAtHead 就得写成这样void addAtHead(int val) { Node* newNode new Node(val); if (head nullptr) { head newNode; } else { newNode-next head; head newNode; } }看到那个 if 了吗空链表和非空链表的插入逻辑被拆成了两条路。deleteAtIndex(0) 更麻烦要删除头节点时你得直接修改 head 指针if (index 0) { Node* toDelete head; head head-next; delete toDelete; size--; return; }这类特判写多了代码里全是分支而每多一个分支就多一个出错的机会。你可能会在某个分支里忘了更新 head可能在某个分支里忘了 size--。实际写下来你会发现大量错误都集中在这些头节点特殊处理的地方。2.2 虚拟头节点让所有操作口径统一虚拟头节点的思路很简单在真正的头节点前面再加一个哨兵节点 dummyHead它的 val 无所谓通常初始化为 0它的 next 才指向链表的第一个真实节点。这样一来链表永远有一个带头的前驱所有操作都可以统一成同一套逻辑从 dummyHead 出发走 index 步到达目标位置的前驱然后进行插入或删除。带虚拟头节点之后addAtHead 就变得和 addAtIndex(0, val) 一模一样不需要任何判断void addAtHead(int val) { Node* newNode new Node(val); newNode-next dummyHead-next; dummyHead-next newNode; size; }空链表也不怕了因为空链表时 dummyHead-next 是 nullptr直接接上去就行。deleteAtIndex(0) 同样不需要特判删除头节点和删除任意节点走的是同一条代码路径。你可以这么理解虚拟头节点就像一个引导位排队时所有人都从它后面开始数第 0 个人就是真实队伍的第一个。操作员永远面对一个非空的队列骨架自然不用纠结队伍空了怎么办。2.3 size 字段就是越界判断的底气类里除了虚拟头节点我还强烈建议维护一个 size 字段记录当前链表中的真实节点数量。原因非常直接get、deleteAtIndex 需要判断 index size 就返回addAtIndex 需要判断 index size 就返回。如果没有 size你要判断索引是否合法只能先遍历整个链表数出长度代价 O(n)而且代码写起来绕来绕去完全没有必要。size 是一个典型的元数据字段每次插入操作加一每次删除操作减一保持和链表实际长度同步。很多初学者写完之后忘记在某个方法里更新 size结果就是链表操作本身没错但越界判断整体失效LeetCode 上显示出错的位置莫名其妙。这里我建议把插入必 、删除必 --当成一条铁律写完每个方法后第一时间检查有没有动 size。需要特别提醒的是addAtIndex 的边界判断用的是 index size而不是 index size。因为 index size 是合法的表示在尾部之后追加节点等价于 addAtTail。这个细节很多人会记反我后面会再提。3. 五方法逐一手写从 get 到 delete 的完整闭环3.1 get(index)走 index 步取目标节点的值get 是最简单的方法但细节照样不少。正确写法是int get(int index) { if (index 0 || index size) return -1; Node* cur dummyHead-next; while (index--) { cur cur-next; } return cur-val; }先做越界判断这里用的是 index size因为 size 是合法索引的下一个位置等于 size 时已经越界。然后 cur 从 dummyHead-next 出发也就是从真正的头节点开始走 index 步。为什么不能从 dummyHead 开始走因为 dummyHead 是第 -1 个位置从它走 index 步到达的是第 index-1 个节点也就是前驱而不是目标节点。get 要取的是目标节点的值所以要跳过虚拟头节点。这个细节虽然小却很容易被忽视。我见过不少人在 get 里写 cur dummyHead然后 index-- 循环结果读到的永远比预期晚一个位置。排查这种问题最笨也最有效的方法就是把链表每次变化后的内容打印出来对照着人肉模拟一遍循环。3.2 addAtHead 与 addAtTail一头一尾逻辑完全对称addAtHead 刚才已经给出核心就是两步接线新节点的 next 先指向旧头节点再把 dummyHead 的 next 指向新节点。void addAtHead(int val) { Node* newNode new Node(val); newNode-next dummyHead-next; dummyHead-next newNode; size; }这两句话的顺序绝对不能写反。如果把 dummyHead-next newNode 写在前面旧头节点就彻底找不到了链表断成两截后面所有操作都会出错。你可以把这一步想象成换挂车厢新车厢必须先挂到旧车厢上再把火车头挂到新车厢上。先动火车头旧车厢就掉队了。addAtTail 则是从 dummyHead 出发一路找到最后一个节点然后把新节点接上去void addAtTail(int val) { Node* cur dummyHead; while (cur-next ! nullptr) { cur cur-next; } Node* newNode new Node(val); cur-next newNode; size; }这里从 dummyHead 出发而不是从 dummyHead-next 出发是为了兼容空链表。空链表时 cur 就是 dummyHeadcur-next 是 nullptr循环不执行新节点直接接在虚拟头节点后面完美。如果不用虚拟头节点空链表时你得单独处理 head newNode又是一次特判。这就是虚拟头节点值钱的地方头插和尾插在边界情况下都不需要条件分支。3.3 addAtIndex(index, val)前驱定位 两步接线addAtIndex 是逻辑上最完整的一个方法因为它要同时处理头部插入、中间插入、尾部插入和非法索引四种情况。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; }注意这里 cur 从 dummyHead 出发走 index 步后cur 指向的是待插入位置的前驱节点。比如 index 0 时cur 就是 dummyHead新节点插到虚拟头节点之后正好是头部插入index size 时cur 是最后一个节点newNode-next cur-next 也就是 nullptr新节点成为新的尾节点正好是尾部追加。一整套逻辑全靠前驱定位这一个思路统一起来不需要任何特殊分支。你可能想问addAtHead 和 addAtTail 能不能直接调用 addAtIndex 实现技术上当然可以addAtHead 等价于 addAtIndex(0, val)addAtTail 等价于 addAtIndex(size, val)。但面试和竞赛里我还是建议拆开写原因有二一是面试官想看到你对每个操作的边界都有清晰认知而不是靠一个万能方法糊弄过去二是拆开后每个方法职责明确阅读起来更直观调试定位也更快。3.4 deleteAtIndex(index)删节点容易难在找前驱删除操作最容易踩的坑在于你要走到的是前驱节点而不是目标节点本身。因为单链表没有前驱指针想要断开目标节点你必须拿到它前面那个节点才能修改 next。void deleteAtIndex(int index) { if (index 0 || index size) return; Node* cur dummyHead; while (index--) { cur cur-next; } Node* toDelete cur-next; cur-next toDelete-next; delete toDelete; size--; }当 index 0 时cur 就是 dummyHeadtoDelete 是真正的头节点cur-next toDelete-next 相当于把虚拟头节点直接接到了第二个节点上头节点被安全移除。当 index size-1 时cur 是倒数第二个节点toDelete 是尾节点toDelete-next 是 nullptrcur-next 被置空尾节点被移除。这里有个 C 特有的关键点delete toDelete。链表节点是用 new 动态分配的如果删除了却忘记释放每次删除操作都会泄漏一块内存。在 LeetCode 上一两个用例可能看不出问题但放到长时间运行的工程里内存泄漏会逐步累积最后程序崩溃。Python 和 Java 因为没有手动内存管理这一步由垃圾回收代劳但理解被删节点需要释放这个语义依然重要。4. 边界问题、典型坑位与面试追问4.1 我亲手踩过的四个坑第一个坑是插入顺序写反。addAtHead 里如果把 dummyHead-next newNode 写在 newNode-next dummyHead-next 之前链表会直接断掉。我自己最早学链表时犯过这个错当时调试了很久才发现是两句交换的问题。从那以后我写插入操作的固定习惯是先接后面再接前面先让新节点指向旧后继再让前驱指向新节点顺序永远不会乱。第二个坑是 index 边界条件记混。addAtIndex 用 index size 判断非法get 和 deleteAtIndex 用 index size 判断非法这两个很容易互相抄错。一旦写错最常见的结果是 addAtIndex(size, val) 被当成非法操作忽略尾插失效或者 deleteAtIndex(size-1) 被判定越界尾节点删不掉。解决方法是把每个方法单独记忆add 的合法区间是 [0, size]get/delete 的合法区间是 [0, size-1]。第三个坑是忘记维护 size。插入不加一、删除不减一链表实际长度和 size 字段就对不上了。刚开始刷题时我犯过几次症状非常迷惑某些用例过了某些用例偶发报错因为越界判断取决于 size 是否正确。排查这类问题最有效的办法是把 size 和链表内容一起打印一目了然。第四个坑是 delete 之后继续访问节点。C 里 delete toDelete 之后toDelete 这块内存已经归还给系统但指针变量的值还保留着如果再访问 toDelete-next 或者 toDelete-val属于未定义行为程序可能崩溃也可能输出随机值。所以一定要在 delete 之前把 toDelete-next 保存到 cur-next也就是先断开、再释放、最后才把删除操作收尾。4.2 边界条件自查清单照着测就完事下面这张表是我每次写完链表类之后必跑一遍的测试清单全部通过基本上就不会有大的逻辑问题操作输入预期行为get空链表 get(0)返回 -1getget(-1)返回 -1getget(size)返回 -1addAtHead空链表新节点成为唯一节点addAtTail空链表新节点成为唯一节点addAtHead连续多次节点依次前插顺序正确addAtTail连续多次节点依次追加顺序正确addAtIndexindex0等价头部插入addAtIndexindexsize等价尾部插入addAtIndexindexsize1忽略且 size 不变deleteAtIndexindex0删除头节点deleteAtIndexindexsize-1删除尾节点deleteAtIndexindexsize忽略且 size 不变我建议你每跑完一组操作就把整个链表从头到尾打印一遍同时打印 size。这个习惯能帮你快速定位错在哪一步而不是靠眼睛盯代码干猜。排查链表问题人肉模拟 打印输出永远是最直接的组合拳。4.3 面试官顺着这道题会追问什么写完之后面试官一般不会就这么放过你。最常见的追问是addAtTail 每次都是 O(n)能优化吗答案是维护一个 tail 指针让尾插变成 O(1)。但要提醒你tail 指针的维护是有代价的删除尾节点时你得知道它的前驱是谁单链表做不到 O(1) 找前驱除非改造成双向链表。这个追问的潜台词是考察你对优化带来的新问题有没有感知。另一个常见追问是能不能改成双向链表每个节点加一个 prev 指针删除操作就不需要遍历找前驱了等于用空间换时间。这个变形和 LeetCode 的设计链表其实是一脉相承的很多面试官会让你现场改一版。还有追问是如何判断链表有环如何找到环的入口如何反转链表这些问题基本都能由 707 自然延伸出来所以认真做完这道题相当于给链表这个专题打了一个扎实的地基。5. 参考实现C、Python、Java 三版本对照5.1 C手动内存管理最练基本功C 版本里我采用 struct 定义节点内部成员放在类的私有区域构造函数负责初始化 dummyHead 和 size。完整的实现如下class MyLinkedList { private: struct Node { int val; Node* next; Node(int val) : val(val), 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 toDelete-next; delete toDelete; size--; } };C 版本最容易踩的坑就是内存泄漏和野指针。deleteAtIndex 里 delete toDelete 这一步千万不能省。另外构造函数里 new 出来的 dummyHead 在析构函数里也要释放LeetCode 不要求写析构但工程代码里这是基本素养。嵌入式领域的链表常客尤其要注意这一点底层内存管理出了问题排查成本非常高。5.2 Python引用语义让代码更简洁Python 没有指针node 之间的连接本质上是通过引用赋值完成的。好处是不用手动释放内存坏处是如果你不理解引用就是隐式指针照样会写出对象串不起来的代码。完整实现class Node: def __init__(self, val): self.val val self.next None class MyLinkedList: def __init__(self): self.dummy_head Node(0) 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 Node(val) new_node.next self.dummy_head.next self.dummy_head.next new_node self.size 1 def addAtTail(self, val: int) - None: cur self.dummy_head 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_head for _ in range(index): cur cur.next new_node Node(val) new_node.next cur.next cur.next new_node self.size 1 def deleteAtIndex(self, index: int) - None: if index 0 or index self.size: return cur self.dummy_head for _ in range(index): cur cur.next cur.next cur.next.next self.size - 1Python 版本里我没有定义len这类魔法方法因为 LeetCode 只要求实现题目给的五个操作保持接口干净就好。你可能会好奇为什么 deleteAtIndex 不需要像 C 那样保存中间节点原因是 Python 没有手动内存管理cur.next cur.next.next 就已经完成了断链被断开的节点对象会被垃圾回收自动处理。5.3 Java内部类写法最贴近真实工程Java 版的实现思路和 C 完全一致区别在于用内部类定义节点且不需要手动释放内存。完整实现class MyLinkedList { private class Node { int val; Node next; Node(int val) { this.val val; } } private Node dummyHead; private int size; public MyLinkedList() { dummyHead new Node(0); size 0; } public 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; } public void addAtHead(int val) { Node newNode new Node(val); newNode.next dummyHead.next; dummyHead.next newNode; size; } public void addAtTail(int val) { Node cur dummyHead; while (cur.next ! null) { cur cur.next; } cur.next new Node(val); size; } public void addAtIndex(int index, int val) { if (index 0 || index size) return; Node cur dummyHead; for (int i 0; i index; i) { cur cur.next; } Node newNode new Node(val); newNode.next cur.next; cur.next newNode; size; } public void deleteAtIndex(int index) { if (index 0 || index size) return; Node cur dummyHead; for (int i 0; i index; i) { cur cur.next; } cur.next cur.next.next; size--; } }Java 的这个写法和 JDK 源码里 LinkedList 的设计思想是相通的虽然 JDK 用的是双向链表但内部节点类 哨兵节点 size 字段这套骨架完全一致。如果你后续要去读 JDK 源码带着这道题的理解去读会顺畅很多。实际工程项目里自己手写链表的机会不算多但理解这种内部类组织数据和维护元信息的方式对读源码、设计数据结构都很有帮助。我个人在实际操作中的体会是这道题最大的价值不在会做而在能做对。很多算法题你看了题解觉得自己懂了关上页面一写全是错。707 就是那面照妖镜能照出你对节点、指针、边界条件的理解到底到了什么层次。如果你现在写这个类还需要翻答案我建议先别急着往下刷题把这张边界条件清单翻来覆去测到全过再去做反转链表、合并有序链表、环形链表这几个经典题你会明显感到顺手很多。链表这块一旦打通后面树的遍历、图的邻接表理解起来都会快一截。