**一. 題目描述** Given a linked list, determine if it has a cycle in it.? Follow up: Can you solve it without using extra space? **二. 題目分析** 題目的意思是給定一個鏈表的頭指針，快速判斷一個鏈表是不是有環，如果有環，返回環的起始位置。該題的經典做法是使用兩個指針，兩個指針均指向頭結點，其中一個是快指針，一次走兩步；另一個是慢指針，一次只走一步，當兩個指針相遇時，證明有環。這種方法的時間復雜度為`O(n)`，空間復雜度`O(1)`，這里需要考慮一些特殊情況： * 空鏈表無環 * 鏈表只有一個節點時可能構成自環 **三. 示例代碼** ~~~ #include <iostream> struct ListNode { int value; ListNode* next; ListNode(int x) :value(x), next(NULL){} }; class Solution { public: bool hasCycle(ListNode *head) { if (head == nullptr || head->next == nullptr) return false; ListNode* fast = head; ListNode* slow = head; while (fast->next->next) { fast = fast->next->next; slow = slow->next; if (fast == slow) return true; } return false; } }; ~~~ 鏈表只有一個節點且該節點構成自環：  鏈表3->4->5->6->7，4->5->6->7形成環：  **四. 小結** 關于有環鏈表中快慢指針一定會相遇的解決方法，可以簡單地證明： 如果有環的話，快慢指針都會進入有環的部分。 而一旦進入有環的部分，一快一慢，學過物理都知道，其實可以相當于一個靜止另一個每次移動一格。 到此，為什么一定會相遇應該已經很明顯了吧~ 該方法廣為人知，不知是否有更為精妙的解法？