用于检测线性数据结构中的循环的弗洛伊德循环检测算法
FloydCycle是一种循环检测算法,用于检测给定单链表中的循环。
在弗洛伊德循环算法中,我们有两个最初指向头部的指针。在兔子和乌龟的故事中,兔子的移动速度是乌龟的两倍,每当兔子到达路径的尽头,乌龟就会到达路径的中间。
算法
在List的头节点初始化Hare和Tortoise。
最初,兔子的移动速度是乌龟的两倍。
移动兔子和乌龟,看看兔子是否到达链表的末尾,返回,因为链表中没有循环。
否则,兔子和乌龟都会前进。
如果Hare和Tortoise在同一个节点上,则返回,因为我们找到了列表循环。
否则,从第2步开始。
上述算法的伪代码
tortoise := headNode hare := headNode foreach: if hare == end return 'There is No Loop Found.' hare := hare.next if hare == end return 'No Loop Found' hare = hare.next tortoise = tortoise.next if hare == tortoise return 'Cycle Detected'