題目描述：給一個(gè)鏈表，判斷其中是否有環(huán)，要求空間復(fù)雜度O(1)。

分析：判斷是否有環(huán)，即在一次鏈表的遍歷過程中是否會(huì)出現(xiàn)重復(fù)訪問同一結(jié)點(diǎn)的情況。單鏈表若有環(huán)則一定是在尾結(jié)點(diǎn)的next指針指向了前面某個(gè)結(jié)點(diǎn)。可以設(shè)一個(gè)數(shù)組記錄訪問過的結(jié)點(diǎn)，出現(xiàn)重復(fù)訪問即有環(huán)。但要求空間復(fù)雜度為常數(shù)，故利用快慢指針，從同一起點(diǎn)出發(fā)，快指針每次走兩步，慢指針每次走一步，若兩者相遇則有環(huán)。至于為什么兩者一定會(huì)相遇，直觀的想象是操場跑圈，既然都在一個(gè)圈上跑，而且一快一慢則快的一定能追上慢的。時(shí)間復(fù)雜度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;
    }
};