bra*_*boy 9 algorithm linked-list cycle
这是面试问题之一.如何查找具有循环的链表的长度.我知道如何使用Hare和Tortoise技术来计算链表是否有周期.我甚至知道如何通过在hashset中存储地址来计算长度.算法的运行时间应为O(n).
但我无法分辨的是如何在不使用O(n)的外部空间的情况下计算链表的长度.请帮我.谢谢.
Vik*_*kas 23
我想如果你知道循环的起始节点,你可以知道循环的长度,从而知道链表中的节点总数.
要获得起点,您只需要O(1)空间.
假设你的两个指针,快速和慢速在'节点t'遇到.
递增一个指针指向下一个节点.和另一个指向链接列表开始的指针.现在递增两个指针直到它们相遇.
会合点是循环的起始节点.
由此您可以通过再次遍历获得循环长度,因为您知道循环的起点.
一旦检测到周期,就需要计算周期的长度和周期的开始位置.这些的总和是列表中不同节点的总数.详细信息例如:http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare