Floyd龟兔赛跑算法，用来解决链表中环的问题，leetcode链接
理论证明
-
首先兔子一次走两步，乌龟一次走一步。在若干次后，如果链表有环，他们一定会相遇。证明如下：
（显然的问题，当他们进入环以后，快指针每次移动都是向慢指针靠近一个位置）
-
在相遇过后，由于乌龟走的长度可以被证明是环长的整数倍.证明如下：
设从链表开头到环的开头的距离是k，环的长度为n，他们第一次相遇的时候，在环上走的长度(小于n的那个)设为m，则可以这样表示：
兔子走的长度为：k+n*i(i为一个未知的正整数)+m ①
乌龟走的长度为：k+n*j(j为一个比i小的未知的正整数)+m ②
这样式①—式②可得，乌龟走的长度为：n(i-j)，又n*(i-j)=m+k+j\n (式②)—>这里化简左右式，可以得到，m+k一定是n的倍数
❗注意，这里相减可以得到的原因是由于兔子走的长度是乌龟走的2倍
-
接着让乌龟回到起点开始走，兔子一次走一步。这样当他们再次相遇的时候，他们的相遇的点就是链表中环的起点。证明如下：
剩下的长度为(m+k)%n一定为0，设m+k=ni。k=n\i-m
当乌龟走了k步时，乌龟到达了环的起点，兔子也走了k步，这个时候兔子的相对位置x= k+m(m为他们相遇的地方)=n*i—>兔子这个时候也是在环的起点。
ℹ️兔子一次走3步，可能就不会相遇了，很简单的设想相对速度为2，如果他们初始相差距离不是2的倍数，比如9，那么永远都不会相遇，很多人把Floyd算法和跑步类比，这是完全错误的，因为它一次走了固定的距离，而并非连续。就好像我们说芝诺的乌龟悖论一样，实际上从数学极限的角度来说，虽然会有无限多个步骤，但最终如果固定时间的话，距离会收敛。
代码实现
对于lc141，和lc142，都是一样的，我这里使用两种方法解决
public class DetectCycle {
/**
* 找出环形链表的第一个头结点
* 1：使用Floyd算法，数学证明第一次相遇必定在环这里
* 2：使用HashSet，遇到重复的节点就说明找着了
**/
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (true) {
// 链表暂时没有环，只需要判断fast即可
if (fast == null || fast.next == null) {
return null;
}
// 链表可能有环
// 移动指针
slow = slow.next;
fast = fast.next.next;
// 找到链表入口
if (slow == fast) {
break;
}
}
// 接下来从起点重新开始，一次走一步
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
/**
* 判断链表是否有环，跟前面那个快慢指针一模一样，找到交接点直接return就可以了。这里使用HashSet
**/
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
HashSet<ListNode> set = new HashSet<>();
ListNode curr = head;
while (true) {
if (curr.next == null) { // next==null就说明没环了
break;
}
if (set.contains(curr)) { // 发现有相同的了
return true;
} else { // 正常遍历
set.add(curr);
curr = curr.next;
}
}
return false;
}
}
文章评论
Hey there! Do you know if they make any plugins to assist with Search Engine
Optimization? I'm trying to get my site to rank for some
targeted keywords but I'm not seeing very good gains.
If you know of any please share. Thank you! I saw similar blog here: <a href="https://Www.Ecobij.nl/">Eco blankets</a>
If you happen to like to travel, there are tons of jobs that embody travel as a focus of the job, together with travel publicist, resort manager, freelance author or photographer, airline pilot and cruise ship director.
<A HREF=https://amieujue470146.bluxeblog.com/61253782/unveiling-the-truth-behind-defender-of-sugar-the-sweetness-may-be-fading>sugar defender</A> As someone that's always bewared about my blood
sugar, locating Sugar Defender has been a relief. I really feel a lot more in control, and my current examinations have
actually revealed positive renovations. Understanding I have a reputable supplement to sustain my routine offers me comfort.
I'm so happy for Sugar Protector's impact on my health!
<a href='https://poppyxhxj492278.thenerdsblog.com/34549225/unveiling-the-truth-behind-sugar-defender-the-sweetness-may-be-fading'>sugar defender reviews</a>
Including Sugar Protector right into my day-to-day program has been a game-changer for
my overall wellness. As someone that already focuses on healthy and balanced consuming, this supplement has actually provided an added boost of defense.
in my energy levels, and my desire for unhealthy snacks so effortless can have such a profound impact on my
daily life. <a href="https://lilybzwb871938.blogzet.com/unveiling-the-truth-behind-sugar-defender-the-sweetness-may-be-fading-43822916">sugar defender ingredients</a>
<A HREF='https://sugardefender-en-us.com'>sugar defender reviews</A> For several years, I've
fought unpredictable blood sugar level swings that left me really feeling drained pipes and
sluggish. Yet since including Sugar my power levels are currently stable and
consistent, and I no longer hit a wall in the
mid-days. I value that it's a gentle, all-natural approach that does not come with any kind of undesirable negative effects.
It's really changed my life. <a href="https://sugardefender-en-us.com">sugar defender ingredients</a>
Your style is very unique in comparison to other folks I've read stuff from. I appreciate you for posting when you have the opportunity, Guess I will just book mark this page.
Oh my goodness! Impressive article dude! Thank you, However I am going through difficulties with your RSS. I don’t know why I can't subscribe to it. Is there anybody getting the same RSS problems? Anyone who knows the solution can you kindly respond? Thanks.
Pretty! This has been an extremely wonderful article. Thank you for providing this info.