[特殊字符] LeetCode 707. 设计链表：告别边界 Bug，优雅实现单链表

📝 题目描述

707. 设计链表

实现 MyLinkedList 类，支持以下操作：

• get(index)：获取第 index 个节点的值，无效返回 -1。

• addAtHead(val)：在头部插入节点。

• addAtTail(val)：在尾部插入节点。

• addAtIndex(index, val)：在第 index 个节点之前插入。若 index 等于链表长度，则追加到末尾；若 index 大于长度，则不插入。

• deleteAtIndex(index)：删除第 index 个节点（若有效）。

示例

输入：
["MyLinkedList","addAtHead","addAtTail","addAtIndex","get","deleteAtIndex","get"]
[[],[1],[3],[1,2],[1],[1],[1]]
输出：
[null,null,null,null,2,null,3]

解释：
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1); // 链表: 1
myLinkedList.addAtTail(3); // 链表: 1 -> 3
myLinkedList.addAtIndex(1,2);// 链表: 1 -> 2 -> 3
myLinkedList.get(1); // 返回 2
myLinkedList.deleteAtIndex(1);// 链表: 1 -> 3
myLinkedList.get(1); // 返回 3

约束

• 0 <= index, val <= 1000

• 不要使用内置 LinkedList 库

• 最多 2000 次调用

🤔 思路分析

链表操作看似简单，但边界条件（空链表、头插、尾插、index 越界）极易出错。传统的实现方式往往需要单独处理头节点，导致代码重复。

核心痛点

• 插入/删除时，需要知道“前驱节点”。对于头节点，它没有前驱，必须特殊处理。

• 空链表时，head 为 null，直接操作会抛空指针。

解决方案：虚拟头节点（Dummy Head） 在链表头部永久放置一个不存储实际数据的节点（dummyHead），它的 next 指向真正的头节点。这样：

• 空链表时，dummyHead.next = null。

• 任何节点（包括原头节点）都有一个统一的前驱操作逻辑。

🔧 优化前后对比

初始实现的问题片段（部分）
// 在 get 中临时创建虚拟头节点
let dmhead = new this.ListNode(0);
dmhead.next = this.head;

// 在 addAtIndex 中也要创建，然后还要重新赋值 this.head
const dummyHead = new this.ListNode(0);
dummyHead.next = this.head;
// … 操作 …
this.head = dummyHead.next; // 多余

缺点

• 每次操作都新建虚拟节点，浪费内存。

• 代码重复，边界处理分散。

优化后的统一设计

function ListNode(val) {
this.val = val;
this.next = null;
}

var MyLinkedList = function() {
this.dummyHead = new ListNode(0); // 永久虚拟头节点
this.size = 0;
};

之后所有操作都基于 this.dummyHead，无需再判空或特殊处理头部。

✅ 最终优化代码（完整版）

function ListNode(val) {
this.val = val;
this.next = null;
}

var MyLinkedList = function() {
this.dummyHead = new ListNode(0);
this.size = 0;
};

// 辅助方法：获取第 index 个节点的前驱节点（index 范围 [0, size]）
MyLinkedList.prototype.getPrevNode = function(index) {
let cur = this.dummyHead;
for (let i = 0; i < index; i++) {
cur = cur.next;
}
return cur;
};

MyLinkedList.prototype.get = function(index) {
if (index < 0 || index >= this.size) return -1;
let cur = this.dummyHead;
// 走 index+1 步到达目标节点（因为 dummyHead 是第 -1 个节点）
for (let i = 0; i <= index; i++) {
cur = cur.next;
}
return cur.val;
};

MyLinkedList.prototype.addAtHead = function(val) {
this.addAtIndex(0, val);
};

MyLinkedList.prototype.addAtTail = function(val) {
this.addAtIndex(this.size, val);
};

MyLinkedList.prototype.addAtIndex = function(index, val) {
if (index < 0 || index > this.size) return;
const prev = this.getPrevNode(index);
const newNode = new ListNode(val);
newNode.next = prev.next;
prev.next = newNode;
this.size++;
};

MyLinkedList.prototype.deleteAtIndex = function(index) {
if (index < 0 || index >= this.size) return;
const prev = this.getPrevNode(index);
prev.next = prev.next.next;
this.size–;
};

📖 核心方法详解

1️⃣ getPrevNode(index)

• 作用：返回第 index 个节点的前驱。

• 注意：当 index = 0 时，前驱是 dummyHead；当 index = size 时，前驱是尾节点（用于尾部插入）。

• 为什么有用：插入和删除都只需要前驱节点。

2️⃣ addAtIndex(index, val)

• 先通过 getPrevNode 拿到前驱。

• 新节点指向 prev.next，再让 prev.next 指向新节点。

• 无需单独处理 index === 0 的情况，因为此时 prev === dummyHead，逻辑完全一致。

3️⃣ deleteAtIndex(index)

• 同样拿到前驱，然后 prev.next = prev.next.next 跳过待删除节点。

• 被跳过的节点会在 JavaScript 中被垃圾回收。

4️⃣ get(index)

• 从 dummyHead 开始向后走 index + 1 步（因为走 1 步到第 0 个节点）。

• 也可以复用 getPrevNode(index+1) 然后取 prev.val，但为了清晰，独立实现。

5️⃣ addAtHead & addAtTail

• 直接复用 addAtIndex，代码量瞬间减少，且逻辑统一。

⏱ 复杂度分析

若想将 addAtTail 优化到 O(1)，可增加一个 tail 指针，但要注意同步维护。对于本题，O(n) 完全可以接受（调用次数 ≤ 2000）。

💡 进阶思考：双向链表

如果题目要求双向链表，只需在 ListNode 中加入 prev 属性，并在插入/删除时同步维护前后指针。同时维护 tail 指针可以让尾部操作达到 O(1)。

双向链表插入示例（插入到 prev 之后）：

newNode.prev = prev;
newNode.next = prev.next;
if (prev.next) prev.next.prev = newNode;
prev.next = newNode;

🎉 总结

通过引入永久虚拟头节点和统一前驱查找，我们实现了：

• ✅ 边界条件零特殊处理（空链表、头插、尾插统一）

• ✅ 代码复用度高，易读易维护

• ✅ 完全满足题目要求

这道题虽小，但蕴含着重要的设计思想：用一个额外的哨兵节点，消除临界情况，让逻辑更优雅。希望这篇文章能帮你彻底掌握链表的实现细节。

如果觉得有帮助，欢迎点赞、收藏、评论交流～

下期预告：用双链表 + 尾指针实现 O(1) 的尾部插入，敬请期待！