图解算法通识讲义线性结构
链表基石与哨兵指针设计
核心心智模型：穿针引线，哨兵保底；断链前必先留后路，虚拟头节点化解一切空指针边界。
核心交互式算法图解演练沙盒
链表双指针模型
单链表三指针就地反转演练
步骤 1 / 5
prev:null
curr:Node(1)
next:Node(2)
curr
1
2
3
4
5
口诀：先存 next，再指 prev；prev 走一步，curr 走一步空间 O(1) · 时间 O(N)
初始化指针：prev=null, curr=Node(1), 预先暂存 next=curr.next (Node 2) 防止链表断裂失联。
关键操作与时空复杂度速查对照表
| 操作 / 算法阶段 | 平均时间 | 最坏时间 | 空间复杂度 | 核心底层机制 |
|---|---|---|---|---|
| 头部插入 / 删除 | O(1) | O(1) | O(1) | 修改指针引用即可，无需数组的数据整体搬迁。 |
| 按序查找 / 随机访问 | O(N) | O(N) | O(1) | 无法利用索引随机寻址，必须循链推进。 |
template.java
ListNode dummy = new ListNode(0, head);
ListNode curr = dummy;
while (curr.next != null) {
if (curr.next.val == val) {
curr.next = curr.next.next;
} else {
curr = curr.next;
}
}
return dummy.next;解题核心心法提炼
- 任何涉及头节点可能被删除或变更的题目，第一行必建 dummyHead。
- 快慢指针解决判环（Floyd 判圈算法）与查找倒数第 K 个节点。
- LRU 缓存机制将哈希表与双向链表结合，达成 O(1) 的存取与访问顺序更新。
常见踩坑警示与避坑指南
- 丢失 next 指针：在没有缓存的情况下直接赋值 curr.next = ... 导致链表后半段断裂。
- 环形链表遍历时缺少 fast.next != null 检查，抛出空指针异常。
对应 Hot 100 实战题目突围
原理已掌握！立即进入沉浸式工作台开始实战演练，强化代码肌肉记忆