Given a linked list, return the node where the cycle begins. If there is no cycle, return?null.
Note:?Do not modify the linked list.
Follow up:
Can you solve it without using extra space?
?
思路：維護兩個指針slow和fast。先判斷是否存在環。
在判斷是否存在環時，slow每次向前移動一步，fast每次移動兩步。
假設從鏈表頭開始一共移動了K次，則fast一共移動了2K步。
兩個指針在相遇時，fast一定比slow多跑了至少一個整環。設鏈表中環長為R，
則有2K - K = nR, 即K = nR。
再看slow所跑過的過程，設鏈表頭到環開始的節點距離為S，環內跑了mR + D，
則有K = S + mR + D。其中，D為slow和fast相遇點在單圈內距離環起點的距離。
與上面比較得 S + mR + D = nR。進一步得 S + D = (n - m)R。
這說明了：在環內，距離環起點D處繼續走S步，會得到整數倍的環長，即會回到環起點處。
而巧的是，S正好也是從鏈表頭到環起點處的距離。
因此，我們有了解法：在判斷是否存在環這一步中，當slow和fast相遇后，令slow=head，然后兩個指針這次都一步一步往前走，這次兩者相遇的地方就是環的起點！
算法時間復雜度O(n), 空間復雜度O(1)。
1 class Solution { 2 public: 3 ListNode *detectCycle(ListNode *head) { 4 if (head == NULL) return NULL; 5 ListNode* slow = head; 6 ListNode* fast = head; 7 while (fast && fast->next) 8 { 9 slow = slow->next; 10 fast = fast->next->next; 11 if (fast == slow) break; 12 } 13 if (fast == NULL || fast->next == NULL) 14 return NULL; 15 slow = head; 16 while (slow != fast) 17 { 18 slow = slow->next; 19 fast = fast->next; 20 } 21 return slow; 22 } 23 };
?
