環(huán)形鏈表

問題：
給你一個鏈表的頭節(jié)點 head ，判斷鏈表中是否有環(huán)。
如果鏈表中有某個節(jié)點，可以通過連續(xù)跟蹤 next 指針再次到達，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評測系統(tǒng)內(nèi)部使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。注意：pos 不作為參數(shù)進行傳遞 。僅僅是為了標識鏈表的實際情況。
如果鏈表中存在環(huán) ，則返回 true 。 否則，返回 false 。
來源：力扣（LeetCode）環(huán)形鏈表

思路一：暴力解法
我們從頭遍歷鏈表，每遍歷一個節(jié)點，就再從頭檢查該節(jié)點是否已經(jīng)出現(xiàn)過，如果直到遍歷完也沒出現(xiàn)則為false，反之為true。這是我們首先可以想到的暴力解法！時間復雜度O(N^2)空間復雜度O(1)。

思路二：快慢指針
我們創(chuàng)建兩個指針slow與fast,讓他們同時指向頭節(jié)點，slow每次走一步，fast每次走兩步。如果循環(huán)最后的結果是 slow=fast 那么鏈表是環(huán)，如果 fast=nullptr 那么鏈表不是環(huán)。

道理跟兩個人一起跑步是一樣的，跑道是環(huán)狀的，且一直跑，那么快的那個人一定會在同一起跑線開始跑后再一次追上慢的人。
代碼：

class Solution {
public:bool hasCycle(ListNode *head) {ListNode* slow=head;ListNode* fast=head;while(slow && fast && fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast){return true;}}return false;}
};

易錯點：

鏈表中環(huán)的入口節(jié)點

問題：
給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點。 從鏈表的頭節(jié)點開始沿著 next 指針進入環(huán)的第一個節(jié)點為環(huán)的入口節(jié)點。如果鏈表無環(huán)，則返回 null。
為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環(huán)。注意，pos 僅僅是用于標識環(huán)的情況，并不會作為參數(shù)傳遞到函數(shù)中。
說明：不允許修改給定的鏈表。
來源：力扣（LeetCode）鏈表中環(huán)的入口節(jié)點

思路：
先證明鏈表有環(huán)，然后再找入口節(jié)點。假如有環(huán)，那么我們一定是slow走的距離是fast走的距離的二分之一，且看下圖分析

代碼：

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* slow=head;ListNode* fast=head;while(slow && fast && fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast){break;}}if(fast==nullptr || fast->next==nullptr){return nullptr;}slow=head;while(slow!=fast){slow=slow->next;fast=fast->next;}return fast;}
};