海口自助建站软件,网站做网站,线上营销推广方案模板,wordpress 改网站域名原题链接#xff1a;https://leetcode.cn/problems/linked-list-cycle/description/
目录
1. 题目描述
2. 思路分析
3. 代码实现 1. 题目描述 2. 思路分析
整体思路#xff1a;定义快慢指针fast#xff0c;slow#xff0c;如果链表确实有环#xff0c;fast指针一定会…原题链接https://leetcode.cn/problems/linked-list-cycle/description/
目录
1. 题目描述
2. 思路分析
3. 代码实现 1. 题目描述 2. 思路分析
整体思路定义快慢指针fastslow如果链表确实有环fast指针一定会在环内追上slow指针。
即慢指针一次走一步快指针一次走两步两个指针从链表起始位置开始运行如果链表带环则一定会在环中相遇否则快指针率先走到链表的末尾。 我们简化一下这个问题用一个线段表示前面的不带环部分的链表用一个圆圈表示带环部分的链表 。 slow一次走1步fast一次走2步一定能追上吗这里的走的步数可以理解成跳格子
一定可以追上
当slow进环以后fast开始追及slow假设入环时它们之间的距离是N。每追及1次它们之间的距离缩小1。当它们之间的距离为0时就追上了。 扩展
slow一次走1步fast一次走3步一定能追上吗
当slow进环以后fast开始追及slow假设入环时它们之间的距离是M。每追及1次它们之间的距离缩小2。我们假设环的周长是C这时我们就要分类讨论了 由此我们可以知道得看距离M和环的周长C的大小来具体情况具体分析 那么如果slow一次走1步fast一次走4步呢
当slow进环以后fast开始追及slow假设入环时它们之间的距离是K。每追及1次它们之间的距离缩小3。我们假设环的周长是C这时我们就要分类讨论了 由此我们可以知道得看距离K和环的周长C的大小来具体情况具体分析 3. 代码实现
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head) {struct ListNode *fasthead,*slowhead;while(fastfast-next){fastfast-next-next;slowslow-next;if(slowfast)return true;}return false;
}
