题目描述
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
解题思路
查看一个链表中是否有环的经典解题思路就是使用快慢指针（双指针），即一个慢指针和快指针同时从头节点出发，如果链表中有环，则两指针在之后一定会相遇，否则，不相遇。其中，慢指针的步长为1，而快指针的步长为2。
-
证明
如图所示，假设链表中某节点a到节点b有环，节点a到节点b之间有m个节点。
image
令慢指针p1（步长为1），快指针p2（步长为2），同时从头节点出发，假设在p1走了K步之后和p2在环内某节点处相遇，则：
2 * p1走的步数 = p2走的步数，即 2K=K+a(m+2)，解得K=a*(m+2)。显然，当m取任何自然数时，都能取到K值，即这个式子是可解的。
当链表中没有环时，显然快指针会先于慢指针到达链表尾，两个指针不会再相遇。
因此，当快慢指针再次相遇时，说明链表中存在环。
代码
/**
* 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;
}
};
