废话不多说!! 直接开干,上题目!!! 环形链表1
其实思路很简单,大家看了题解肯定能了解了,那我现在就来解释一下其中的数学问题!!追击问题! 本题其实就是说我们有一个环形链表,如果没环就false,有环就true,那么怎么判断呢? 我们设置一个快慢指针,如果是有环的话,那么这两个指针都会进入环中循环,由于速度不一样,这就好比我们在操场上追人一样,一定能追上, 但是问你为什么能追上你能说清楚嘛?? 大家如果知道相对运动就很简单了,路程差=速度差×追及时间,能理解了吧!! 代码:
bool hasCycle(struct ListNode *head) {
struct ListNode *fast=head;
struct ListNode *slow=head;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
if(fast==slow)
return true;
}
return false;
}
这题可能过于简单,那我们看下题!!!!
环形链表2 这你还会吗? 如果大家看过这题,或者官方题解的话,那我们看下题解怎么说的: 我打箭头的地方大家知道为什么吗??
我解释一下,我们可以通过路程关系推出 a=c+(n-1)(b+c),也就是说
那么,prt指向这个链表的头位置,慢指针动一步,prt动一步,当慢指针跑到环形入口时,prt到环形入口距离是不是还有(n-1)(b+c),我们一看这不是圆形距离的整数倍嘛,而且慢指针现在还在入口处,等我们prt到入口的时候,那慢指针是不是跑了整数倍的环长,也来到了入口处,所以当他们两个相等时找到入口位置!!!
这不就理解了嘛,可能大佬感觉简单,但是对于我们这种小菜鸡还是得多多总结的!! 喜欢的点个关注吧,铁子们!
|