原題鏈接：https://leetcode.cn/problems/linked-list-cycle/description/
目錄
1. 題目描述
2. 思路分析
3. 代碼實現(xiàn)
1. 題目描述
2. 思路分析
整體思路：定義快慢指針fast，slow，如果鏈表確實有環(huán)，fast指針一定會在環(huán)內(nèi)追上slow指針。
即慢指針一次走一步，快指針一次走兩步，兩個指針從鏈表起始位置開始運行，如果鏈表帶環(huán)則一定會在環(huán)中相遇，否則快指針率先走到鏈表的末尾。
我們簡化一下這個問題，用一個線段表示前面的不帶環(huán)部分的鏈表，用一個圓圈表示帶環(huán)部分的鏈表 。
?
slow一次走1步，fast一次走2步，一定能追上嗎？（這里的走的步數(shù)可以理解成跳格子）
一定可以追上！
當slow進環(huán)以后，fast開始追及slow，假設入環(huán)時，它們之間的距離是N。每追及1次，它們之間的距離縮小1。當它們之間的距離為0時，就追上了。
?
?
擴展：
slow一次走1步，fast一次走3步，一定能追上嗎？
當slow進環(huán)以后，fast開始追及slow，假設入環(huán)時，它們之間的距離是M。每追及1次，它們之間的距離縮小2。我們假設環(huán)的周長是C，這時我們就要分類討論了：
由此我們可以知道，得看距離M和環(huán)的周長C的大小來具體情況具體分析！
那么如果slow一次走1步，fast一次走4步呢？
當slow進環(huán)以后，fast開始追及slow，假設入環(huán)時，它們之間的距離是K。每追及1次，它們之間的距離縮小3。我們假設環(huán)的周長是C，這時我們就要分類討論了：
?由此我們可以知道，得看距離K和環(huán)的周長C的大小來具體情況具體分析！文章來源：http://www.zghlxwxcb.cn/news/detail-662447.html
3. 代碼實現(xiàn)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool hasCycle(struct ListNode *head) {
struct ListNode *fast=head,*slow=head;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
if(slow==fast)
return true;
}
return false;
}
文章來源地址http://www.zghlxwxcb.cn/news/detail-662447.html
到了這里，關于【數(shù)據(jù)結(jié)構OJ題】環(huán)形鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
