題目：見leetcode141
解答：
官方解答
解法一：雙指針
bool hasCycle(ListNode *head) {
if(head == nullptr || head->next == nullptr)
{
return false;
}//一個元素不算環(huán)
ListNode *slow = head;
ListNode *fast = head->next;//
while(slow != fast)
{
if(fast == nullptr || fast->next == nullptr)
{
return false;
}
slow = slow->next;
fast = fast->next->next;
}
return true;
}
時間復雜度：n，空間復雜度：1//快慢兩個指針
注：時間復雜度分析：以慢指針為角度，進入環(huán)之前，經(jīng)過N個結(jié)點；進入環(huán)之時蛀醉，慢指針落后快指針N悬襟；進入環(huán)之后衅码，經(jīng)過n-N次循環(huán)慢指針追上快指針。所以時間復雜度為n
24ms;11.6%
優(yōu)化：8ms脊岳；-1.56%
bool hasCycle(ListNode *head) {
ListNode *slow = head;
ListNode *fast = head;
while (fast && fast->next){
slow = slow->next;
fast = fast->next->next;
if (slow == fast){
return true;
}
}
return false;
}
解法二：hash表-發(fā)生沖突即有環(huán)
待提交
時間復雜度：n逝段，空間復雜度：n
待提交
總結(jié)：
1.c++中hashset和hashmap的基本操作
2.同一種解題思路的代碼還可以大幅度優(yōu)化——解法一優(yōu)化之后性能提高了三倍垛玻！
原因分析：應該是因為優(yōu)化前while中比較的為兩個動態(tài)指針，優(yōu)化之后while中比較的為一個動態(tài)指針奶躯。
