題目：
給定一個鏈表蹬铺，判斷鏈表中是否有環(huán)。
為了表示給定鏈表中的環(huán)甜攀，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）秋泄。 如果 pos 是 -1规阀，則在該鏈表中沒有環(huán)。
示例 1:
輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個環(huán)谁撼，其尾部連接到第二個節(jié)點(diǎn)歧胁。
示例 2:
輸入：head = [1,2], pos = 0
輸出：true
解釋：鏈表中有一個環(huán)厉碟，其尾部連接到第一個節(jié)點(diǎn)。
示例 3:
輸入：head = [1], pos = -1
輸出：false
解釋：鏈表中沒有環(huán)箍鼓。
進(jìn)階：
你能用 O(1)（即，常量）內(nèi)存解決此問題嗎款咖？
題目分析：
先說我的想法（獻(xiàn)丑了）：我一開始想用map何暮，key就是每個節(jié)點(diǎn)的地址，一直遍歷下去郭卫，如果某個key出現(xiàn)了兩次砍聊，那么就是環(huán)形鏈表了贰军。
后來看到進(jìn)階提到用O(1)內(nèi)存解決問題玻蝌，再參考一下網(wǎng)上大神的解法词疼，感覺我的想法好幼稚~
正解分析：設(shè)置一個快指針，一個慢指針贰盗，快指針每次走兩個许饿，慢指針每次走一個舵盈。
- 如果沒有環(huán)陋率，那么遍歷一次就結(jié)束了秽晚。
- 如果有環(huán)，那么快指針一定會繞一圈回來追上慢指針赴蝇。
嘿菩浙！這解法真機(jī)靈喔句伶。
C++代碼如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if (!head || !head -> next) return false;
ListNode* fast = head;
ListNode* slow = head;
bool c = false;
while (fast && fast -> next) {
slow = slow -> next;
fast = fast -> next -> next;
if (fast == slow) {
c = true;
break;
}
}
return c;
}
};
沒圖了
