题目描述：给一个链表，判断其中是否有环，要求空间复杂度O(1)。
分析：判断是否有环，即在一次链表的遍历过程中是否会出现重复访问同一结点的情况。单链表若有环则一定是在尾结点的next指针指向了前面某个结点。可以设一个数组记录访问过的结点，出现重复访问即有环。但要求空间复杂度为常数，故利用快慢指针，从同一起点出发，快指针每次走两步，慢指针每次走一步，若两者相遇则有环。至于为什么两者一定会相遇，直观的想象是操场跑圈，既然都在一个圈上跑，而且一快一慢则快的一定能追上慢的。时间复杂度O(n)，空间O(1)。
代码：
/**
* 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) {
ListNode *slow = head, *fast = head;
while (fast && fast -> next)
{
slow = slow -> next;
fast = fast -> next -> next;
if (slow == fast) return true;
}
return false;
}
};
