指针跳跃与链表排名

每轮把当前后继替换为后继的后继，同时把两段距离相加，跳跃长度因而成倍增长。双缓冲让所有节点都读取同一个旧轮次，整个链在 $O(\log n)$ 轮内压到 null；这换来低深度，却在朴素实现中重复处理全部节点而多付一个对数 work。

四节点状态轨迹 ​

原链为 a→b→c→d→null。初态距离是 (1,1,1,0)。

第一轮使用旧快照：a 跳到 c、距离 2；b 跳到 d、距离 2；c 跳到 null、距离 1；d 保持 0。第二轮 a 读取 c 的旧状态，得到 null 与距离 $2+1=3$；b 读取 d，距离仍为 2。

最终 (3,2,1,0) 正是到尾排名。若第一轮更新 c 后立刻让 a 读新 c，a 会提前跨越不同倍数，其他节点又仍在旧层；算法可能在简单链上碰巧得到距离，却不再有统一轮次证明。

Work、depth 与处理器 ​

朴素方案每轮让所有 $n$ 个节点做常数工作，共 $O(\log n)$ 轮，因此

低 depth 并不等于 work-optimal：串行遍历只需 $O(n)$ 工作。经典 work-optimal list ranking 会随机或确定性选独立节点集合、把它们从链中 splice out，递归排名缩短后的链，再反向恢复被删节点，分析与单纯 pointer jumping 不同。

在 $P<n$ 时，直接按 Brent 调度给 $O(n\log n/P+\log n)$，仍保留额外对数工作。若只写“对数时间”，就隐藏了使用 $n$ 处理器和超线性 work 的条件。

PRAM 冲突规则 ​

单链上的非空后继映射在每轮仍为单射：不同原位置向前跳相同的 $2^t$ 步，不会落到同一个非空位置。先用一个读取子步让各处理器读取自身旧记录，再用另一个读取子步读取非空后继的旧记录；每个子步内目标都互异。最后各自写入新缓冲，因此这套常数子步实现可在 EREW PRAM 上运行，保持同样的渐近轮数与工作量。

若输入改成多个节点共享后继的函数图，单射性就不成立，后继读取可能需要 CREW 或额外复制、调度。双缓冲负责旧新轮次分离，地址单射性负责排他读取；两份证明承担不同作用。

与 binary lifting 的区别 ​

倍增表理路二进制倍增Binary lifting · Doubling technique预计算函数的 $2^k$ 次迭代，用输入步数的二进制展开快速跳转。预处理 up[v][j]，保留所有 $2^j$ 祖先以回答许多查询，空间 $O(n\log n)$。Pointer jumping 在每轮覆盖当前指针，用并行破坏式压缩换取一次全体排名，通常只保留 $O(n)$ 状态。

两者都用倍增不变量，但本算法不调用预先保留全部层的倍增表，接口也不同：前者是静态查询索引，后者是并行收缩过程。需要恢复原链时，必须另存初始 next，不能指望最终全部为 null 的数组仍含结构。

失败边界 ​

输入若含环，就没有尾距离，pointer jumping 会在环上周期跳转而不终止为 null。应先验证链结构、指定一个断点，或把问题改成 functional graph 的环检测与距离分解。

边带权时把初始 dist[v] 设为边权，更新仍用加法；负权不影响有限链求和，但可能溢出。多个不相交链可同时排名，尾节点各自为 0；共享尾的树形结构则不再是一条链，排名语义要重新定义。