无锡网站建设的公司,wordpress foxlogin,中国域名注册,做电商的常去网站题目#xff1a; 示例#xff1a; 分析#xff1a;
这道题属于是那种知道解法就很简单#xff0c;不知道解法就很难独立想出来的那种#xff0c;我们只需要稍微记住这类题的固定解法就可以。
所以接下来我先说解法#xff0c;再解释为什么解法可以解出来。
那么我们都…题目 示例 分析
这道题属于是那种知道解法就很简单不知道解法就很难独立想出来的那种我们只需要稍微记住这类题的固定解法就可以。
所以接下来我先说解法再解释为什么解法可以解出来。
那么我们都知道使用快慢指针可以找出一个链表是否有环不知道的去看看我昨天的每日一题题解我们需要找出这个环的路口我们在快慢指针相遇的时候就可以判断出链表有环并且开始寻找。
我们将快指针移动回链表的开头并且将快指针的速度调整为每次移动一格然后再让快慢指针再次移动直到它们相遇相遇的位置就是环的入口。
这看起来有些不可思议是吗怎么会这么简单而且怎么就可以知道它们再次相遇的点就是环入口了小朋友你是否有很多问号
那么这涉及到了数学因此这类题我的建议就是记住对应的模板不要深究怎么样才可以在下次遇到类似的题目时自己可以从零开始推导出来这不是普通人能干的。
首先我们把链表开头到环入口的这段距离称为A把环入口到快慢指针第一次相遇的地方的这段距离称为B把快慢指针第一次相遇的地方直走走回环的入口的这段距离称为C接下来可以开始推导了。 我们知道快指针走过的的路程等于ABCB而慢指针走过的路程等于AB。
我们又知道每次快指针移动两格慢指针移动一格因此快指针走过的路程是慢指针的两倍。
我们就可以得到这样的式子 ABCB 2*AB AABB 化简一下就变成了 CA 神奇吗同志们从链表到环入口的距离A就等于在快慢指针第一次相遇的地方再次走到环入口因此我们之前的操作就可以得到解释了让慢指针接着走然后让快指针调整速度以后从头开始走走到它们第二次相遇那就是环的入口了。 代码
class Solution {
public:ListNode *detectCycle(ListNode *head) {if(headnullptr) return nullptr;//快慢指针ListNode* fasthead;ListNode* slowhead;while(fast!nullptr fast-next!nullptr){//快指针每次移动两次,慢指针每次移动一次slowslow-next;fastfast-next-next;//如果相遇则是有环,开始寻找入口if(fastslow){fasthead;while(fast!slow){fastfast-next;slowslow-next;}return fast;}}return nullptr;}
};
