題目鏈接👉 LeetCode 141.環形鏈表👈

💡題目分析

給你一個鏈表的頭節點 head ，判斷鏈表中是否有環。

如果鏈表中有某個節點，可以通過連續跟蹤 next 指針再次到達，則鏈表中存在環。 為了表示給定鏈表中的環，評測系統內部使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。注意：pos 不作為參數進行傳遞 。僅僅是為了標識鏈表的實際情況。

如果鏈表中存在環 ，則返回 true 。 否則，返回 false 。

💡解題思路

快慢指針：
定義兩個指針，一個快指針、一個慢指針，讓快指針一次走一步，慢指針一次走兩步，如果存在環的話，快指針會先進環，一直在環中循環的走，等到慢指針也進入環中循環，快指針追擊慢指針，最后它們一定會相遇（因為快慢指針的差距步是一步），就可以判斷出該鏈表存在環；如果不存在環的話，快指針會走到頭結束。

👇過程圖解👇

🔔接口源碼

//快慢指針
bool hasCycle(struct ListNode *head) 
{struct ListNode* fast = head, *slow = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){return true;}}return false;
}

💡深度思考

?思考1

slow一次走一步，fast一次走兩步，slow和fast一定會相遇嗎？

fast會先進環，slow會后進環，假設slow進環時，slow和fast之間的距離為N，slow進環以后，fast開始追擊slow，slow每走1步，fast每走2步，他們之間距離縮小1。
追擊過程中，他們之間的距離變化：N，N-1，N-2，… ，2，1，0

所以一定會相遇！

?思考2

slow一次走一步，fast一次走三步，slow和fast一定會相遇嗎？

fast會先進環，slow會后進環，假設slow進環時，slow和fast之間的距離N，slow進環以后，fast開始追擊slow，slow每走1步，fast每走3步，他們之間距離縮小2

由于環的長度不同，追擊過程中，他們之間的距離變化會有兩種情況（奇/偶）：

所以不一定會相遇！

🥰希望烙鐵們能夠理解歐！

總結🥰
以上就是本題講解的全部內容啦🥳🥳🥳🥳
本文章所在【C/C++刷題系列】專欄，感興趣的烙鐵可以訂閱本專欄哦🥳🥳🥳
前途很遠，也很暗，但是不要怕，不怕的人面前才有路。💕💕💕
小的會繼續學習，繼續努力帶來更好的作品😊😊😊
創作寫文不易，還多請各位大佬uu們多多支持哦🥰🥰🥰