目錄

1.問題? ? ??

2.證明

3.代碼實現(xiàn)

---

1.問題? ? ??

????????給你一個鏈表的頭節(jié)點?head?，判斷鏈表中是否有環(huán)。

????????如果鏈表中有某個節(jié)點，可以通過連續(xù)跟蹤?next?指針再次到達(dá)，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評測系統(tǒng)內(nèi)部使用整數(shù)?pos?來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。注意：pos?不作為參數(shù)進(jìn)行傳遞?。僅僅是為了標(biāo)識鏈表的實際情況。

????????如果鏈表中存在環(huán)?，則返回?true?。 否則，返回?false?。

?????????

2.證明

? ? ? ? 使用快慢指針的方法可以很簡單的達(dá)到目的，慢指針每次走一步快指針每次走兩步，如果在鏈表中存在環(huán)，入環(huán)以后快慢指針沒走一次，他們直接的距離就會減一，直至最后它們會在環(huán)里面相遇，如圖：?

? ? ? ? 思考一個問題，快指針必須走兩步嗎，快指針每次走三步行不行，四步呢？五步呢？N步行不行？

? ? ? ? 假設(shè)快指針每次走三步，當(dāng)慢指針入環(huán)時，它們同時向后走，每次它們之間的距離會減少2，但是如果它們之間的距離是奇數(shù)，那么他們這次就不會相遇，極限清空下，他們每次的距離都是奇數(shù)的話，那么他們是不是就永遠(yuǎn)不會相遇了，走N步的道理也是一樣的。如圖：

?

3.代碼實現(xiàn)

typedef struct ListNode Node;
bool hasCycle(struct ListNode *head) 
{//金典的快慢指針法//快指針每次走兩步，慢指針每次走一步，//快指針先進(jìn)環(huán)，慢指針后進(jìn)環(huán)//在環(huán)的里面每走一次快慢指針直接的距離縮小1//最終快指針會追上慢指針//如果最終不想交說明鏈表沒有環(huán)Node* slow = head;Node* fast = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;if(slow == fast){//在環(huán)里面相遇return true;}}return  false;
}