**一. 題目描述** 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; } }; ~~~ 一個有環鏈表，環從第二個節點開始：  **四. 小結** 解答與鏈表有關的題目時，要多畫圖，找規律，否則容易遇到各種邊界問題。