LeetCode 707. 设计链表
目录
题目描述
题意分析
要从零实现一个链表类，对外暴露五个操作：按下标取值、头部插入、尾部插入、指定下标插入、指定下标删除。下标从 0 开始计数。
真正决定实现难度的是各个操作对非法下标的约定，题面写得很细而且并不统一：get 遇到越界要返回 -1 而不是报错；addAtIndex 允许 index 恰好等于当前长度，此时等价于追加到末尾，只有严格大于长度时才什么都不做；deleteAtIndex 遇到越界则静默忽略。这三种约定各不相同，是本题最主要的失分点。
约束方面调用次数只有两千级，说明单次操作走 $O(n)$ 的遍历完全够用，题目考的不是复杂度，而是能不能把指针操作和边界写干净。另外要注意插入位置合法的下标范围是 [0, size]，而取值与删除位置合法的下标范围是 [0, size - 1]，两者差一。
解法：哨兵节点 + 单链表
核心思路
最朴素的写法是直接用一个 head 指针表示链表。这样每个写操作都要分裂成两套逻辑：往头部插入要改 head 本身，往中间插入要改前驱节点的 next；删除第 0 个节点要改 head，删除其他节点要改前驱的 next。五个方法乘以两套分支，写出来又长又容易漏。
瓶颈不在时间，而在于「头部」这个位置没有前驱节点，导致它必须被特殊对待。
观察到只要在真正的首节点前面额外挂一个不存放业务数据的节点，这个特殊性就消失了：此时任何一个合法位置都存在前驱，头部插入退化成「在这个额外节点后面插入」，删除第 0 个节点退化成「改这个额外节点的 next」。分支从两套合并成一套。
整个类由两条不变量支撑。其一，dummy 这个节点永远存在、永远不被删除、它的值永远不参与任何答案，链表的真实首节点始终是
dummy.next。其二，size 恒等于 dummy 之后真实节点的个数，任何一次成功的插入让它加一、任何一次成功的删除让它减一。有了这两条，对任意满足 $0 \le index \le size$ 的下标，从 dummy 出发走 index 步一定能落在「第 index 个节点的前驱」上，五个方法都可以复用这一段定位代码。
解题步骤
- 构造函数里建出 dummy 节点并把 size 置 0。dummy 的值取什么都无所谓，因为不变量保证它不会被读到。
- get：先用
index < 0 || index >= size挡掉越界并返回 -1，再从dummy.next出发走 index 步。这里从dummy.next起步而不是从 dummy 起步，是因为要拿的是节点本身而不是它的前驱。- addAtIndex：先挡掉
index > size的非法调用，注意是严格大于，因为等于 size 表示合法的尾部追加；index 为负则按题面语义夹到 0。然后从 dummy 出发走 index 步拿到前驱，再做插入。- 插入的两行赋值必须先写
node.next = prev.next再写prev.next = node。顺序反了的话prev.next已经被改成新节点，新节点的 next 就会指向自己，链表当场成环。- addAtHead 与 addAtTail 直接转调 addAtIndex，参数分别是 0 和 size。复用而不是重写，是为了让边界判断只存在一份。
- deleteAtIndex：越界判断用
index >= size而不是index > size，因为可删除的最大下标是 size - 1；拿到前驱后一行prev.next = prev.next.next完成摘除，最后 size 减一。以官方样例的调用序列走一遍：初始时链表为空，size = 0，只有 dummy。addAtHead(1) 转调 addAtIndex(0, 1)，
0 > 0不成立，前驱走 0 步就是 dummy，插入后链表为 1，size = 1。addAtTail(3) 转调 addAtIndex(1, 3)，1 > 1不成立，前驱从 dummy 走 1 步到达值为 1 的节点，插入后链表为 1 -> 3，size = 2。addAtIndex(1, 2)，1 > 2不成立，前驱仍是值为 1 的节点，新节点的 next 先接上原来的 3，再让 1 指向 2，链表变成 1 -> 2 -> 3，size = 3。get(1)，下标合法，从dummy.next也就是值 1 的节点出发走 1 步到达值 2 的节点，返回 2。deleteAtIndex(1)，下标合法，前驱从 dummy 走 1 步到值 1 的节点，把它的 next 从 2 改成 3，链表变成 1 -> 3，size = 2。最后 get(1)，从值 1 的节点走 1 步到值 3 的节点，返回 3。整段输出依次是 2 和 3，与预期一致。
代码实现
// get、addAtIndex、deleteAtIndex 均先定位到前驱节点再操作。
class MyLinkedList {
private final ListNode dummy;
private int size;
public MyLinkedList() {
dummy = new ListNode(0);
size = 0;
}
public int get(int index) {
if (index < 0 || index >= size) {
return -1;
}
ListNode cur = dummy.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur.val;
}
public void addAtHead(int val) {
addAtIndex(0, val);
}
public void addAtTail(int val) {
addAtIndex(size, val);
}
public void addAtIndex(int index, int val) {
if (index > size) {
return;
}
if (index < 0) {
index = 0;
}
ListNode prev = dummy;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
ListNode node = new ListNode(val);
node.next = prev.next;
prev.next = node;
size++;
}
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) {
return;
}
ListNode prev = dummy;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
prev.next = prev.next.next;
size--;
}
private static class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
}
// get、addAtIndex、deleteAtIndex 均先定位到前驱节点再操作。
type MyLinkedList struct {
dummy *ListNode
size int
}
type ListNode struct {
Val int
Next *ListNode
}
func Constructor() MyLinkedList {
return MyLinkedList{dummy: &ListNode{Val: 0}, size: 0}
}
func (l *MyLinkedList) Get(index int) int {
if index < 0 || index >= l.size {
return -1
}
cur := l.dummy.Next
for i := 0; i < index; i++ {
cur = cur.Next
}
return cur.Val
}
func (l *MyLinkedList) AddAtHead(val int) {
l.AddAtIndex(0, val)
}
func (l *MyLinkedList) AddAtTail(val int) {
l.AddAtIndex(l.size, val)
}
func (l *MyLinkedList) AddAtIndex(index int, val int) {
if index > l.size {
return
}
if index < 0 {
index = 0
}
prev := l.dummy
for i := 0; i < index; i++ {
prev = prev.Next
}
node := &ListNode{Val: val, Next: prev.Next}
prev.Next = node
l.size++
}
func (l *MyLinkedList) DeleteAtIndex(index int) {
if index < 0 || index >= l.size {
return
}
prev := l.dummy
for i := 0; i < index; i++ {
prev = prev.Next
}
prev.Next = prev.Next.Next
l.size--
}
复杂度分析
- 时间复杂度：单次操作 $O(n)$，其中 n 是链表当前长度。get、addAtIndex、deleteAtIndex 都要从 dummy 走到目标前驱，最坏走满整条链；addAtHead 走 0 步是 $O(1)$，addAtTail 因为是单链表且没有维护尾指针，仍然是 $O(n)$。
- 空间复杂度：$O(n)$，除 dummy 与 size 这两个常数级字段外，只为每个已插入的元素各留一个节点。
关键点总结
- 哨兵节点的价值不是省一行代码，而是消除「头部没有前驱」这个唯一的特例，让所有位置在结构上变得同质；凡是链表题里出现「可能改到头节点」的字样，都该条件反射加 dummy。
- 把 addAtHead 和 addAtTail 实现成对 addAtIndex 的转调，保证边界判断只有一份，改一处就全对；设计类题目里这种收敛入口的做法比性能优化更值钱。
- 显式维护 size 让三个方法的越界判断都变成 $O(1)$ 的比较，否则每次都要先数一遍链表长度；用一个冗余字段换掉重复遍历，是设计题的常见取舍。
- 插入时先接后继再改前驱，这个赋值顺序是硬性的，反过来就自环；同理删除时要先把后继取出来再改指针。
- 面试视角：这题几乎必定被追问「怎么让 addAtTail 变成 $O(1)$」，标准答案是再维护一个 tail 指针，但必须同时说清它带来的负担——删除尾节点时单链表拿不到新的尾节点前驱，所以要么改成双向链表，要么接受删除仍是 $O(n)$。能主动谈这个代价，比直接说「加个 tail 就行」高一档。
- 面试视角：写之前先把五个方法各自的越界约定复述一遍再动手，面试官会认为你在读题而不是背模板；这题的失分几乎全部来自边界，而不是指针操作本身。
易错点总结
- 错误写法：addAtIndex 的非法判断写成
index >= size就返回：新建对象后调用 addAtTail(1)，此时 index 与 size 都是 0 → 追加被拒绝，链表永远是空的，后续所有 get 都返回 -1。- 错误写法：deleteAtIndex 的越界判断写成
index > size：链表为 1，调用 deleteAtIndex(1) → 前驱走到值 1 的节点，prev.next已经是 null，执行prev.next.next直接空指针异常。- 错误写法：定位前驱的循环写成
for (int i = 0; i <= index; i++)：链表为 1 -> 3 时调用 addAtIndex(1, 2) → 前驱多走一步落到值 3 的节点，结果变成 1 -> 3 -> 2，插入位置整体后移一格。- 错误写法：插入时先写
prev.next = node再写node.next = prev.next：任意一次插入 → 新节点的 next 指向它自己，链表成环，之后任何一次遍历都会死循环。- 错误写法：get 里从 dummy 而不是
dummy.next起步：addAtHead(1) 之后调用 get(0) → 走 0 步停在 dummy 上，返回哨兵的占位值 0，而不是 1。- 错误写法：addAtHead 直接写成
dummy.next = new ListNode(val)：连续调用 addAtHead(1)、addAtHead(2) → 新节点没有接住原来的链，链表只剩 2，前面插入的数据全部丢失。- 错误写法：插入或删除成功后忘记同步 size：连续两次 addAtTail 之后 → addAtTail 仍按 size 为 0 定位，新元素被反复插到头部，同时 get 的越界判断也会把合法下标判为非法。
- 错误写法：get 越界时抛异常或返回 0：链表为 1 -> 3 时调用 get(2) → 题目要求返回 -1，返回 0 会被判成错误答案，抛异常则直接运行时错误。
- 错误写法：把 addAtIndex 中 index 为负的情况和
index > size合并成一个「非法就返回」的分支：调用 addAtIndex(-1, 5) → 按题面语义应当插到头部，直接返回会丢掉这次插入。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 146. LRU 缓存 | 中等 | 双向链表配合哈希表，要求所有操作都是 $O(1)$ |
| 155. 最小栈 | 中等 | 用辅助栈维护历史最小值，考的是冗余状态的同步 |
| 232. 用栈实现队列 | 简单 | 双栈倒腾实现顺序反转，考摊还复杂度分析 |
| 622. 设计循环队列 | 中等 | 定长数组加取模下标，难点是区分队空与队满 |
| 705. 设计哈希集合 | 简单 | 手写散列与拉链法冲突处理 |
| 706. 设计哈希映射 | 简单 | 在 705 基础上额外维护键值对的更新语义 |
| 1206. 设计跳表 | 困难 | 多层链表加随机层高，把查找降到期望 $O(\log n)$ |