**一. 题目描述** Given a linked list, return the node where the cycle begins. If there is no cycle, return null.  Follow up: Can you solve it without using extra space? **二. 题目分析** 在Linked List Cycle题目中，使用了两个指针fast与slow检查链表是否有环，该题在此基础上，要求给出链表中环的入口位置，同样需要注意空间复杂度。为了方便解释，以下给出一个有环链表：  其中，设链表头节点到环入口处的距离为`X`，环长度为`Y`，使用`fast`和`slow`两个指针，`fast`指针一次前进两步，`slow`指针一次前进一步，则他们最终会在环中的`K`节点处相遇，设此时`fast`指针已经在环中走过了`m`圈，`slow`指针在环中走过`n`圈，则有： `fast`所走的路程：`2*t = X+m*Y+K` `slow`所走的路程：`t = X+n*Y+K` 由这两个方程可得到： `2X + 2n*Y + 2K = X + m*Y + K` 进一步得到： `X+K = (m-2n)Y` **从`X+K = (m-2n)Y` 可发现，X的长度加上K的长度等于环长度Y的整数倍！**因此可得到一个结论，即当`fast`与`slow`相遇时，可使用第三个指针`ListNode* cycleStart = head;`，从链表头节点往前走，`slow`指针也继续往前走，直到`slow`与`cycleStart`相遇，该位置就是链表中环的入口处。 **三. 示例代码** ~~~ #include <iostream> using namespace std; struct ListNode { int value; ListNode* next; ListNode(int x) :value(x), next(NULL){} }; class Solution { public: ListNode *detectCycle(ListNode *head) { if (head == NULL || head->next == NULL || head->next->next == NULL) return head; ListNode* fast = head; ListNode* slow = head; while (fast->next->next) { fast = fast->next->next; slow = slow->next; if (fast == slow) { ListNode* cycleStart = head; while (slow != cycleStart) { slow = slow->next; cycleStart = cycleStart->next; } return cycleStart; } } return NULL; } }; ~~~ 一个有环链表，环从第二个节点开始：  **四. 小结** 解答与链表有关的题目时，要多画图，找规律，否则容易遇到各种边界问题。