网站建设肆金手指排名6,松江网站开发培训学校,建设香帅摩托车官网,百度账号购买1元40个Lei宝啊#xff1a;个人主页
愿所有美好与我们不期而遇 题目描述 #xff1a;
给你一个链表的头节点 head #xff0c;判断链表中是否有环。
接口#xff1a;
bool hasCycle(struct ListNode *head)
示例1#xff1a; 示例2#xff1a; 返回值#xff1a;
true或…
Lei宝啊个人主页
愿所有美好与我们不期而遇 题目描述
给你一个链表的头节点 head 判断链表中是否有环。
接口
bool hasCycle(struct ListNode *head)
示例1 示例2 返回值
true或false
思路 使用快慢指针 快的追慢的如果有环在相对速度差合适的情况下就可以追得到返回true无环就返回false这里我们采取速度差为1每一次相对距离接近1最后快的追上慢的。 实现代码
bool hasCycle(struct ListNode* head) {struct ListNode* slow head;struct ListNode* fast head;while (fast fast-next){slow slow-next;fast fast-next-next;if (slow fast){return true;}}return false;
} 该速度差为一也就是说每次两者的距离都会靠近一所以一定追得上那么速度差为n时什么情况我们追不上呢 当距离差为N,N是偶数速度差为偶数追得上。N是奇数速度差为偶数就会错过然后错过后两者的相对距离还要再次判断和计算是否为偶数从而产生了永远也追不上的可能性。速度差为奇数也是同样的道理这里就体现出速度差为1的好处他一定追得上而不用去考虑是否有可能会永远也追不上。