链表总结（哑节点 · 常见坑 · 复杂度分析）
easy-medium链表设计模式总结
哑节点（Dummy Node）模式
几乎所有链表修改题都应该加哑节点，原因：
- 头节点可能被删除/替换
- 避免大量 null 判断
ListNode dummy = new ListNode(0, head);
// ... 操作 ...
return dummy.next; // 真正的头节点
常见坑点
1. 忘记断尾
链表原本 A → B → C → D，操作后 A、C 组成一个链表，但 B 仍然指向 C，会导致环：
// 错误：忘记将 greater 尾部截断
ListNode greater = new ListNode(0);
// ...
greater.next = null; // 必须加这一行！
2. 循环条件里的 null 检查顺序
// 正确：先检查 fast，再检查 fast.next
while (fast != null && fast.next != null) { ... }
// 错误：可能 NullPointerException
while (fast.next != null && fast != null) { ... }
3. 修改全局变量时忘记保存
// 错误：head 已被修改，后续无法恢复
while (head != null) { head = head.next; }
// 正确：用临时指针
ListNode cur = head;
while (cur != null) { cur = cur.next; }
常用技巧汇总
| 技巧 | 适用场景 |
|---|---|
| 哑节点 | 头节点会被修改的题 |
| 快慢指针 | 找中间、找环、倒数第k |
| 递归 | 分治（归并排序）、反转 |
| 两次遍历 | 先找长度，再操作 |
| 栈 | 正序变逆序（两数相加II） |
链表 vs 数组
| 操作 | 链表 | 数组 |
|---|---|---|
| 随机访问 | O(n) | O(1) |
| 头部插入/删除 | O(1) | O(n) |
| 中间插入/删除（已知位置） | O(1) | O(n) |
| 空间 | 每个节点有额外指针 | 连续内存 |
| 缓存友好 | 差（指针跳跃） | 好 |
重要链表题清单
基础操作：
✅ 206 反转链表
✅ 92 反转链表II
✅ 25 K个一组翻转
✅ 24 两两交换
双指针：
✅ 876 链表中点
✅ 141 环形链表I
✅ 142 环形链表II
✅ 160 相交链表
✅ 19 删除倒数第N个
合并/排序：
✅ 21 合并两个有序链表
✅ 23 合并K个有序链表
✅ 148 排序链表
特殊应用：
✅ 2 两数相加
✅ 445 两数相加II
✅ 234 回文链表
✅ 138 带随机指针的深拷贝
✅ 143 重排链表
✅ 146 LRU缓存
✅ 460 LFU缓存