公司做英文网站,网络广告名词解释,广州市新闻最新消息,免费个人简历模板官网做题链接 目录 前言#xff1a; 一、算法推导#xff1a;
1.假设有环并且一定会相遇#xff0c;那么一定是在环内相遇#xff0c;且是快指针追上慢指针。
2.有环就一定会相遇吗#xff1f;快指针是每次跳两步#xff0c;有没有可能把慢指针跳过去#xff1f;
3.那一定… 做题链接 目录 前言 一、算法推导
1.假设有环并且一定会相遇那么一定是在环内相遇且是快指针追上慢指针。
2.有环就一定会相遇吗快指针是每次跳两步有没有可能把慢指针跳过去
3.那一定会在一圈内相遇吗 二、开始做题
1.注意题目的条件先做特殊情况处理
2.定义快慢指针和注意判断语句
3.完整代码
三、为什么快指针每次走两步而不是三步或更多
1.效率和正确性平衡
2.两步最优 前言 在环形链表问题中使用快指针和慢指针的原因在于这种方法能够高效地检测链表是否包含环。这种方法也称为“龟兔赛跑算法”具体来说让快指针每次移动两步慢指针每次移动一步可以保证在存在环的情况下两指针最终会相遇。 一、算法推导
1.假设有环并且一定会相遇那么一定是在环内相遇且是快指针追上慢指针。 一定会在环内相遇 设慢指针速度为v则快指针速度为2v 走了相同时间t时 满指针走的路程svt则快指针为2s2vt 因此没有环不可能相遇相遇的话必定在环内。 快指针追上慢指针 慢指针不可能追上快指针因为速度没有快指针快永远被落在后面。 只有等快指针跑下一圈时遇上慢指针。就像我们跑800m的时候有些跑得快的同学可以在跑第二圈的时候与有些跑得慢还在跑第一圈的同学相遇。 因此相遇时的情景一定是这样 2.有环就一定会相遇吗快指针是每次跳两步有没有可能把慢指针跳过去 建立认知 如图当快指针在慢指针后面且距离1的时候下一回合就可以相遇。 那当快指针在慢指针后面且距离2、3、4、5、...、n时呢 建立认知: 如图每走一回合两者之间的距离会-1。 也就是说不断的走n-1-1-1-1-1........两者距离一定会减到1。
切入角度1 那么就会发生如下图情况两指针相遇。 切入角度2 不断的走n-1-1-1-1-1........两者距离一定会减到0。此时此刻两指针相遇 3.那一定会在一圈内相遇吗 设一圈的长度为c 入环后两指针的距离为n。则nc。 每一回合n-1最坏情况下当nc时一共需要c个回合n才为0两个指针才能相遇。c个回合慢指针刚好走一圈。因此一圈内肯定会相遇。 二、开始做题
1.注意题目的条件先做特殊情况处理 if(headnull || head.nextnull){return false} 2.定义快慢指针和注意判断语句 如果代码中没有环快指针遍历到终点时会指向空 又因为快指针每次要连跳两格所以要判断一下fast.next避免空指针异常 3.完整代码
public class Solution {public boolean hasCycle(ListNode head) {if(headnull || head.nextnull){return false;}ListNode fasthead;ListNode slowhead;while(fast!null fast.next!null slow!null){fastfast.next.next;slowslow.next;if(fastslow){return true;}}return false;}
} 三、为什么快指针每次走两步而不是三步或更多
1.效率和正确性平衡 如果快指针每次走三步或更多步可能会跳过慢指针使得两者在环内无法相遇或者需要更多的时间和步骤来相遇算法的效率和简单性会下降。 2.两步最优 前人通过大量实际问题和理论证明快指针每次走两步慢指针每次走一步既能保证在环内快速相遇又不会跳过相遇点。
