链表 · 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(n) 但删除 O(1)？三个基础指针功夫：哨兵 dummy head 挂在头节点前，让「删头节点」和「删中间」形式一致，消除特判；只拿到待删节点本身时，用 「覆盖后继再跳过」 做到 O(1) 删除；以及 Linus 用来定义 “good taste” 的 二级指针 (pointer-to-pointer)——让删头与删中间收敛成同一行、彻底无特判，附 C 的好 / 坏品味对照与 JS 的 (owner,key) 槽写法。
反转链表：迭代与递归
链表的经典题目。难点在于 不要丢失后面那一段：核心步骤是「先存 tmp 再改写指向」。迭代版 三指针 prev / cur / tmp 逐个反向、O(1) 空间；递归版 先递归到尾节点（新表头），再在回溯时逐层 head.next.next = head 回指自己。单步看箭头一根根反向、看递归调用栈起落。
结构形态:指针方向 与 首尾相连
指针方向：单向 与 双向链表
节点存一个 next 还是 prev + next？用「删除一个已知节点」拉开差距：单向没有前驱、得从 head 找 → O(n);双向用一个多出来的指针（每节点 +8 字节）换来 x.prev 当场可达 → O(1)，还能反向遍历。单步看查找指针爬行 vs 直接跨过。
循环链表：尾接回头（单 / 双循环）
把尾节点的 next 指回头节点，链表成环——没有 null 终点，遍历靠「回到起点」判停。单向循环 / 双向循环 / 加哨兵逐个切换，演示环形遍历与约瑟夫环（每数 k 个淘汰一人）。双向循环 + 哨兵正是内核 list_head 的形态。
约瑟夫环：模拟 / 递推 / 闭式解
n 人围圈，从 #0 起每数到第 k 个淘汰一人，直到剩一人——求幸存者编号。三条解法做成对等可视 lab:模拟 在循环链表上逐个报数删除 (O(n·k)),递推 用 f(n)=(f(n-1)+k) mod n 把答案从小问题映射回原编号（O(n) / O(1) 空间）,闭式解 在 k=2 时把 n 的二进制最高位绕到末尾即得 (O(1))。三法统一 0-indexed 输出，可相互印证「问题规模缩减 + 编号映射」的递推建模。
性能变体:为查找 / 缓存 / 内存改造节点
跳表：有序链表叠快速通道
有序链表查找只能 O(n) 逐个走。skip list 在其上叠几层稀疏索引，每层跳过若干节点，查找从高层「能跨就跨、跨过头就下沉」，平均降到 O(log n)——以概率层高替代平衡树的旋转。Redis ZSet、LevelDB 都用它。单步看查找路径逐层下沉。
展开链表：一个节点装一小段数组
每个节点不再只存一个值，而是一小段连续数组（如容量 4）。unrolled linked list 是数组与链表的折中：指针开销摊薄、缓存局部性更好；插入挤满时节点分裂 (split)。单步看元素落入哪个节点、满了如何一分为二。Redis quicklist 即此思路。
XOR 链表：两个指针压成一个
双向链表每节点存 prev 和 next 两个地址。XOR linked list 只存一个 both = prev ⊕ next，靠相邻节点地址异或还原指针，省一半指针空间。代价是无法随机持有节点、对 GC / 调试不友好——一道经典的指针位运算 trick。单步看 next = both ⊕ prev 如何复原。
快慢指针:用「速度差」换信息
判环 · 找入口 · 量环长
Floyd 判圈（龟兔赛跑）:slow 一步、fast 两步，有环必相遇，相比 HashSet 法省去 O(n) 空间。相遇之后还能进一步求出 环入口（一指针回表头、同速再走，数学依据 a = kL-b）和 环长（从相遇点绕一圈数步数）。改「尾部接回第几个」构造出不同的环，单步看两指针在环里逼近、相遇、定位。
倒数第 k 个 与 链表中点
单链表只能向前走，却要定位「倒数第 k」「正中间」。思路是先让两指针拉开 固定间距 再齐步走：倒数第 k 让 fast 先独走 k 步，fast 出界时 slow 正好落在答案（删倒数第 k 配合哨兵可消除特判）; 中点 让 fast 两步、slow 一步，fast 到尾 slow 在一半——归并排序链表、判回文的第一步。
两条链表:对齐与拼接
合并两个有序链表
归并排序里的「合并」步。两边各派指针，每次挑更小的节点接到结果尾部——不搬移数据，只改指针。关键是用 哨兵 dummy 作为结果链的起点，tail 一路接下去省去首节点特判；一边走完后把另一边 剩余整段 一并接上。<= 保证稳定性。两行链表 + 结果行同步演示。
两链表相交：找第一个公共节点
两链表共用同一条尾部，形状像 Y。换轨双指针：走完自己接对方，各走 a+c+b 步得以对齐，恰好相遇于公共点（不相交则同到 null）; 长度对齐法：长的先走差值步再齐步同行。还讲「比较尾节点判定是否相交」与有环情形。改三段长度构造相交 / 不相交，观察两指针换轨追逐。
复制:带随机指针的深拷贝
工程应用:真实系统中的链表
🔗 相关链接
- 链表常见问题与解法小结 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 压缩指针的双向链表变体及其局限。