floyd判圈算法
发布网友
发布时间：2022-11-22 03:47
共1个回答
热心网友
时间：2024-12-04 21:59
问题：如何检测一个链表是否有环，如果有，那么如何确定环的起点.
要求 : 空间复杂度为O(1), 时间复杂度为O(n).
假设一个有环链表如下图: 利用floyd判圈算法可以做到下面的三件事:
使用两个指针slow和fast。两个指针都从链表的起始处S开始。slow每次向后移动一步，fast每次向后移动两步。若在fast到达链表尾部前slow与fast相遇了，就说明链表有环。
这里可以简单的证明一下：反证法，假如没有环，那么slow永远追不上fast，那么在fast到达链表尾部前slow不会fast相遇了。若相遇了，链表就有环。
当slow和fast相遇时，slow和fast必定在环上，所以只要让一者不动，另一者走一圈直到相遇，走过的节点数就是环的长度。
如图所示，设AB=n, SA=m。设环的长度为L。
假设slow走过的节点数为i，那么有：
i = m + n + aL a为slow绕过的环的圈数。
因为fast速度为slow的两倍，所以相同时间走过的节点数为slow的两倍，所以有：
2i = m + n + bL b为fast绕过的环的圈数。
两者做差有 : i = (b-a)L。
所以可知，fast和slow走过的距离是环的整数倍。
所以有m+n=L。
所以此时让slow回到起点S，，fast仍然在B。
让两个指针以每次一步的速度往前走。
当走了m步时，可发现slow和fast正好都在A处，即是环的起点。
floyd判圈算法是一个很有趣的算法，在某些题目上用处很大，比如下面这个。
给出一个数组 nums 包含 n + 1 个整数，每个整数是从 1 到 n (包括边界)，保证至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
注意事项
对于这个题目
