一尘不染

计算链接列表中可能是循环的节点数

algorithm

这是问题所在,出自Sedgwick出色的Java算法(q 3.54)

给定一个指向不包含空链接的单链接列表中的节点的链接(即,每个节点都链接到其自身或列表中的另一个节点),则无需修改任何节点且不使用常量内存即可确定不同节点的数量空间。

你怎么做呢?使用野兔和陆龟算法扫描列表一次,以任何方式确定其是否为圆形,然后再次扫描以查看列表变为圆形的地方,然后再次计数以计数到此位置的节点数?对我来说听起来有点蛮力,我想还有更优雅的解决方案。


阅读 244

收藏
2020-07-28

共1个答案

一尘不染

Tortoise_and_hare算法可以给你 在周期开始(λ和分别μ)前的周期长度和节点的数量。

2020-07-28