链表（Linked List）
链表题看起来在操作节点，实际上大多数都在考三件事：找前驱、断开再重连、用双指针控制相对位置。
核心思路
链表是一种线性数据结构，通过指针将一组零散的内存块串联起来使用。每个内存块称为链表的”节点”（Node），除了存储数据外，还需记录链上下一个节点的地址。
核心特点
- 非连续存储：节点在内存中不连续
- 动态大小：可以灵活增删节点
- 指针连接：通过指针维护节点关系
- 无法随机访问：必须从头节点开始遍历
链表类型
1. 单链表（Singly Linked List）
┌────┬────┐ ┌────┬────┐ ┌────┬────┐
│ 1 │ ●──┼───→│ 2 │ ●──┼───→│ 3 │null│
└────┴────┘ └────┴────┘ └────┴────┘
data next data next data next
2. 双向链表（Doubly Linked List）
┌────┬────┬────┐ ┌────┬────┬────┐ ┌────┬────┬────┐
null←┼─● │ 1 │ ●──┼───→│ ● │ 2 │ ●──┼───→│ ● │ 3 │ ●──┼→null
└────┴────┴────┘ └────┴────┴────┘ └────┴────┴────┘
prev data next prev data next prev data next
3. 循环链表（Circular Linked List）
┌────┬────┐ ┌────┬────┐ ┌────┬────┐
┌─→│ 1 │ ●──┼───→│ 2 │ ●──┼───→│ 3 │ ●──┼──┐
│ └────┴────┘ └────┴────┘ └────┴────┘ │
└───────────────────────────────────────────────┘
基本操作
时间复杂度
| 操作 | 单链表 | 双向链表 | 说明 |
|---|---|---|---|
| 访问 | O(n) | O(n) | 需要从头遍历 |
| 搜索 | O(n) | O(n) | 需要遍历 |
| 插入（头部） | O(1) | O(1) | 直接操作 |
| 插入（尾部） | O(n) | O(1)* | *需维护tail指针 |
| 插入（中间） | O(1) | O(1) | 已知前驱节点 |
| 删除（头部） | O(1) | O(1) | 直接操作 |
| 删除（中间） | O(1) | O(1) | 已知前驱节点 |
空间复杂度
- 单链表：每个节点额外存储 1 个指针
- 双向链表：每个节点额外存储 2 个指针
Go 代码
节点定义
type ListNode struct {
Val int
Next *ListNode
}
// 双向链表节点
type DoublyListNode struct {
Val int
Prev *DoublyListNode
Next *DoublyListNode
}反转链表
func reverseList(head *ListNode) *ListNode {
var prev *ListNode
cur := head
for cur != nil {
next := cur.Next
cur.Next = prev
prev = cur
cur = next
}
return prev
}虚拟头节点
func removeNthFromEnd(head *ListNode, n int) *ListNode {
dummy := &ListNode{Next: head}
fast, slow := dummy, dummy
for i := 0; i < n; i++ {
fast = fast.Next
}
for fast.Next != nil {
fast = fast.Next
slow = slow.Next
}
slow.Next = slow.Next.Next
return dummy.Next
}常用技巧
1. 虚拟头节点（Dummy Head）
简化边界条件处理
经典题目
基础操作
双指针技巧
- 链表的中间结点 - LeetCode 876
- 环形链表 - LeetCode 141
- 环形链表 II - LeetCode 142
- 相交链表 - LeetCode 160
- 删除链表的倒数第 N 个结点 - LeetCode 19
链表重组
高级题目
- 排序链表 - LeetCode 148
- 合并K个升序链表 - LeetCode 23
- 复制带随机指针的链表 - LeetCode 138
2. 快慢指针
- 找中点
- 判断有环
- 找环入口
- 删除倒数第
n个节点
链表 vs 数组
| 特性 | 数组 | 链表 |
|---|---|---|
| 内存分配 | 连续 | 离散 |
| 访问速度 | O(1) | O(n) |
| 插入删除 | O(n) | O(1)* |
| 缓存友好 | 是 | 否 |
| 空间利用 | 高 | 低（额外指针） |
| 大小 | 固定/扩容 | 动态 |
*前提是已知插入/删除位置的前驱节点
易错点
链表题几乎所有 bug 都和指针顺序有关，尤其是“先断开还是先保存 next”。
- 改指针前先把
next存下来。 - 涉及头节点删除时，优先上虚拟头节点。
- 快慢指针先把循环条件写稳，再写指针移动。
- 合并 / 反转 / 重排时，最后要检查尾节点是否正确断开。
优缺点
优点
- ✅ 插入删除效率高（已知位置）
- ✅ 动态大小，灵活扩展
- ✅ 不需要连续内存
缺点
- ❌ 无法随机访问
- ❌ 额外存储指针，空间开销大
- ❌ 缓存不友好，局部性差
应用场景
- 频繁插入删除：任务队列、LRU缓存
- 大小不确定：动态数据集合
- 实现其他数据结构：栈、队列、图的邻接表