141. Linked List Cycle

题目描述：给一个链表，判断其中是否有环，要求空间复杂度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;
    }
};