一、什么是链表？
链表（Linked List） 是一种线性数据结构，由若干节点组成，每个节点包含数据和指向下一个节点的指针。
Mermaid · 渲染中（下方为源码）
graph LR N1([1 | ·]) -- next --> N2([2 | ·]) N2 -- next --> N3([3 | ·]) N3 -- next --> N4([4 | ·]) N4 -.-> NULL((null))
特点：
- 不连续存储——节点可散落在内存各处。
- 动态大小——无需预先分配容量。
- 插入删除 O(1)——只需修改指针（已知位置时）。
二、链表 vs 数组
| 操作 | 数组 | 链表 |
|---|---|---|
| 随机访问 | O(1) | O(n) |
| 头部插入 | O(n) | O(1) |
| 尾部插入 | O(1) 均摊 | O(n) / O(1)（带尾指针） |
| 中间插入 | O(n) | O(n)（需先遍历） |
| 内存连续 | ✅ | ❌ |
| 缓存友好 | ✅ | ❌ |
| 额外空间 | 无 | 每节点额外指针 |
选择：随机访问多 → 数组；插入删除多 → 链表。
三、链表分类
3.1 单链表
head → A → B → C → D → null
只能从头到尾遍历，每个节点含一个 next 指针。
3.2 双链表
null ← A ⇄ B ⇄ C ⇄ D → null
每个节点含 prev 和 next 两个指针，可双向遍历。Java 的 LinkedList 就是双链表。
3.3 循环链表
尾节点的 next 指向 head，构成环。
用途：约瑟夫问题、循环调度。
四、单链表实现（Java）
4.1 节点定义
class ListNode {
int val;
ListNode next;
ListNode(int v) { val = v; }
}4.2 虚拟头结点（dummy head）
简化边界处理，统一所有位置的插入/删除逻辑。
public class LinkedListR<E> {
private Node<E> dummyHead;
private int size;
public LinkedListR() {
dummyHead = new Node<>(null);
size = 0;
}
public int getSize() { return size; }
public boolean isEmpty() { return size == 0; }
public void add(int index, E e) {
if (index < 0 || index > size) throw new IllegalArgumentException();
Node<E> prev = dummyHead;
for (int i = 0; i < index; i++) prev = prev.next;
prev.next = new Node<>(e, prev.next);
size++;
}
public void addFirst(E e) { add(0, e); }
public void addLast(E e) { add(size, e); }
public E get(int index) {
if (index < 0 || index >= size) throw new IllegalArgumentException();
Node<E> cur = dummyHead.next;
for (int i = 0; i < index; i++) cur = cur.next;
return cur.val;
}
public E remove(int index) {
if (index < 0 || index >= size) throw new IllegalArgumentException();
Node<E> prev = dummyHead;
for (int i = 0; i < index; i++) prev = prev.next;
Node<E> ret = prev.next;
prev.next = ret.next;
ret.next = null;
size--;
return ret.val;
}
}4.3 链表的递归实现
private Node<E> add(Node<E> node, int index, E e) {
if (index == 0) return new Node<>(e, node);
node.next = add(node.next, index - 1, e);
return node;
}特点：
- 不需要虚拟头结点——递归自然处理位置 0。
- 代码简洁。
- 注意栈溢出——长链表（> 1e4）改迭代。
五、核心技巧
5.1 双指针 / 快慢指针
判环：
boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}找环入口：快慢指针相遇后，一个回 head，一个从相遇点同步走，再次相遇即环入口。
找链表中点：
ListNode middle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}5.2 哨兵节点（dummy）
让"头部插入/删除"和"中间插入/删除"逻辑统一。
ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode cur = dummy;
while (cur.next != null) {
if (cur.next.val == val) cur.next = cur.next.next;
else cur = cur.next;
}
return dummy.next;
}5.3 反转链表
迭代版：
ListNode reverse(ListNode head) {
ListNode prev = null, cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}递归版：
ListNode reverse(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = reverse(head.next);
head.next.next = head;
head.next = null;
return newHead;
}5.4 合并两个有序链表
ListNode mergeTwoLists(ListNode a, ListNode b) {
ListNode dummy = new ListNode(0), tail = dummy;
while (a != null && b != null) {
if (a.val <= b.val) { tail.next = a; a = a.next; }
else { tail.next = b; b = b.next; }
tail = tail.next;
}
tail.next = a != null ? a : b;
return dummy.next;
}六、性能分析（深度）
虽然表面上链表头部插入是 O(1)，但实际常数很大：
- 每插入一个节点都要
new Node()，触发一次堆分配。 - 堆分配涉及系统调用 / GC，比栈 / 数组慢得多。
- 缓存不友好——每次
next可能跳到任意内存地址，CPU cache 失效。
经验：数据量大时（> 1e5），动态数组反而比链表更快，因为 cache locality 优势压过 O(n) 的劣势。
七、链表的工程应用
| 场景 | 使用 |
|---|---|
| LRU 缓存 | 双向链表 + 哈希表 |
| Linux 内核任务队列 | 双向链表 |
| 操作系统进程调度 | 双向链表 |
| 数据库事务 undo log | 双向链表 |
| Git 提交历史 | 链表 |
| 编辑器撤销栈 | 链表 |
八、易错点（面试高频）
- 空指针：
head == null或head.next == null要单独处理。 - 丢链：反转链表时，必须先存
next再改指针。 - 死循环：环检测没判断
fast.next == null会越界。 - 找不到前驱：删除节点需要 prev，没 dummy 时要单独处理头节点。
- 栈溢出：递归深度 = 链表长度，长链表改迭代。
- 值比较：Java 中链表节点用
equals比较，不要用==（除非 int）。
九、链表 vs 其他数据结构
| 场景 | 推荐 |
|---|---|
| 大量随机访问 | 数组 |
| 大量插入删除 | 链表 |
| 既要搜索又要插入 | 跳表 / BST |
| 频繁查最值 | 堆 |
| 范围查询 | 跳表 / B 树 |
十、复杂度汇总
| 操作 | 时间（已知位置） | 时间（未知位置） |
|---|---|---|
| 头部插入 | O(1) | O(1) |
| 尾部插入 | O(1)（带 tail） | O(n) |
| 中间插入 | O(1) | O(n) |
| 头部删除 | O(1) | O(1) |
| 中间删除 | O(1) | O(n) |
| 查找 | O(n) | O(n) |
十一、刷题清单
| 难度 | 题目 | 关键 |
|---|---|---|
| 🟢 | 反转链表 | 双指针 |
| 🟢 | 合并两个有序链表 | dummy + 双指针 |
| 🟢 | 删除链表的节点 | dummy |
| 🟡 | 反转链表 II | dummy + 区段反转 |
| 🟡 | 环形链表 II | 快慢指针 |
| 🟡 | 相交链表 | 双指针追及 |
| 🟡 | 删除链表的倒数第 N 个节点 | 快慢指针 |
| 🟡 | 奇偶链表 | 双指针重组 |
| 🟠 | K 个一组翻转链表 | 模拟 |
| 🟠 | 排序链表 | 归并 / 快慢 |
| 🔴 | LRU 缓存 | 哈希 + 双链表 |
| 🔴 | 二叉树展开为链表 | 链表拼接 |
十二、心法
链表 = 指针的艺术。
面试链表题，dummy 节点 + 双指针能解决 80% 的问题。
写完先画图，再小数据跑通（n=1, 2, 3），最后扩规模。
十三、多语言对照：反转链表
ListNode reverse(ListNode head) {
ListNode prev = null, curr = head;
while (curr != null) {
ListNode nxt = curr.next;
curr.next = prev;
prev = curr;
curr = nxt;
}
return prev;
}