題目描述
給定一個鏈表勃蜘，判斷鏈表中是否有環(huán)仰担。
如果鏈表中有某個節(jié)點统阿，可以通過連續(xù)跟蹤 next 指針再次到達炊林，則鏈表中存在環(huán)姥卢。
解題思路
查看一個鏈表中是否有環(huán)的經(jīng)典解題思路就是使用快慢指針（雙指針），即一個慢指針和快指針同時從頭節(jié)點出發(fā)渣聚，如果鏈表中有環(huán)独榴，則兩指針在之后一定會相遇，否則奕枝，不相遇棺榔。其中，慢指針的步長為1倍权，而快指針的步長為2掷豺。
-
證明
如圖所示，假設鏈表中某節(jié)點a到節(jié)點b有環(huán)薄声，節(jié)點a到節(jié)點b之間有m個節(jié)點当船。
image
令慢指針p1（步長為1），快指針p2（步長為2）默辨，同時從頭節(jié)點出發(fā)德频，假設在p1走了K步之后和p2在環(huán)內(nèi)某節(jié)點處相遇，則：
2 * p1走的步數(shù) = p2走的步數(shù)缩幸，即 2K=K+a(m+2)壹置，解得K=a*(m+2)。顯然表谊，當m取任何自然數(shù)時钞护，都能取到K值，即這個式子是可解的爆办。
當鏈表中沒有環(huán)時难咕，顯然快指針會先于慢指針到達鏈表尾，兩個指針不會再相遇。
因此余佃，當快慢指針再次相遇時暮刃，說明鏈表中存在環(huán)。
代碼
/**
* 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 == NULL || head->next == NULL)
return false;
ListNode* p1 = head;
ListNode* p2 = head->next->next;
while (p1 != p2 && p1 != NULL && p2 != NULL && p2->next != NULL){
p1 = p1->next;
p2 = p2->next->next;
}
return p1 == p2 && p1 != NULL && p2 != NULL && p2->next != NULL;
}
};
