**一. 题目描述** 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形成环：  **四. 小结** 关于有环链表中快慢指针一定会相遇的解决方法，可以简单地证明： 如果有环的话，快慢指针都会进入有环的部分。 而一旦进入有环的部分，一快一慢，学过物理都知道，其实可以相当于一个静止另一个每次移动一格。 到此，为什么一定会相遇应该已经很明显了吧~ 该方法广为人知，不知是否有更为精妙的解法？