链表 · Linked List
链表 (linked list) 把元素串成一条「next 链」,放弃了数组的随机访问,换来 O(1) 的就地插入 / 删除。因为只能顺着 next 单向遍历、改写一个指针就牵动整条链,围绕它的经典问题都在解决同一件事—— 如何用少量指针,在一趟扫描里完成操作、又不丢失链的连接。
全系列顺着「结构 → 操作 → 应用」展开。先打 基础:节点与指针、哨兵 / O(1) 删除 / 二级指针。再看同一条「节点 + 指针」骨架能长成哪些 结构——沿三条轴变形: 指针方向(单向 / 双向)、首尾是否相连(循环)、为性能改造节点(跳表 / 展开 / XOR)。然后是结构之上的经典 算法: 反转、快慢指针(判环 / 定位)、多链表对齐与拼接(合并 / 相交)、 带随机指针的深拷贝。最后在 LRU 缓存 / 跳表 / 邻接表 等真实系统里看这套指针操作的 工程形态。
每页都能修改输入、单步推进,观察指针移动、next 箭头逐根改写、代码逐行高亮。算法页指针统一配色 teal = slow / prev / 链 A、 orange = fast / cur / 链 B、 rose = tmp / tail / 结果;结构页 绿 = next / 主链、 靛蓝 = prev / 后向、 橙 = 查找指针、 玫红 = 当前改写 / 目标,每页顶部另有图例。
基础:指针就是一切
链表基础：哨兵节点 与 O(1) 删除
哨兵消除删头节点的特判；覆盖后继法可在只持有该节点时 O(1) 删除，代价是删掉的实为后继；二级指针把两种情形统一成一个指针槽。
反转链表：迭代与递归
三指针迭代反转与递归反转的对照：后者写法短，代价是 O(n) 栈深，长链上会栈溢出。
结构形态:指针方向 与 首尾相连
指针方向：单向 与 双向链表
单向只能顺着 next 走，双向多存一个 prev 换来已知节点的 O(1) 增删；按值查找两者都是 O(n)。
循环链表：尾接回头（单 / 双循环）
尾节点指回头节点后遍历没有天然终点，判停改用 do…while 与「回到起点」；空环需要哨兵自环兜底。
约瑟夫环：模拟 / 递推 / 闭式解
约瑟夫环的三条解法：循环链表模拟、O(n) 递推，以及 k 等于 2 时的位运算闭式解。
性能变体:为查找 / 缓存 / 内存改造节点
跳表：有序链表叠快速通道
在有序链表上叠几层稀疏索引，查找期望 O(log n)、最坏 O(n)；层高来自抛硬币，实现比平衡树简单。
展开链表：一个节点装一小段数组
每个节点装一小段连续数组，摊薄指针开销、改善缓存局部性；随机访问仍是 O(n)，收益在常数。
XOR 链表：两个指针压成一个
每个节点只存前后地址的异或值，靠上一个地址推出下一个，省一根指针的代价是与 GC 和调试工具全面冲突。
快慢指针:用「速度差」换信息
判环 · 找入口 · 量环长
Floyd 判圈的两阶段：快慢指针必在环内相遇，再由头节点与相遇点同步前进即得入环点。
倒数第 k 个 与 链表中点
固定间距的快慢指针求倒数第 k 个；求中点时两种循环条件在偶数长度上分别取靠后与靠前的那个。
两条链表:对齐与拼接
合并两个有序链表
两条有序链表的归并：迭代版用哨兵简化接头，相等时优先接前一条以保持稳定。
两链表相交：找第一个公共节点
判断两条链表是否相交并找出第一个公共节点：长度对齐法与换轨法都只用 O(1) 额外空间。
复制:带随机指针的深拷贝
工程应用:真实系统中的链表
🔗 相关链接
- 链表常见问题与解法小结 wuchong.me 算法线的选题参考:O(1) 删除、转置、倒数第 k、中点、判环、找环入口、相交判断与公共节点。
- 双指针系列 @vega/playground 快慢指针、左右对撞、同向追赶的系统拆解;与本系列的快慢指针部分互为补充。
- Dancing Links @vega/playground 双向循环链表的极致应用:四向指针织成二维环,删除时不释放指针以便回溯「跳回」。
- Floyd's Tortoise and Hare wikipedia.org 判圈算法的来龙去脉与正确性证明,以及 Brent 算法等改进。
- Linked list wikipedia.org 各类链表的定义、节点布局与权衡综述。
- Skip list wikipedia.org Pugh 1990 提出的概率性有序结构,平均 O(log n) 查找 / 插入。
- XOR linked list wikipedia.org 用 prev ⊕ next 压缩指针的双向链表变体及其局限。