找到鏈表中的環

Contact me:

Blog : https://cugtyt.github.io/blog/index

Email: cugtyt#qq.com, cugtyt#http://gmail.com

題目：

給定一個鏈表，返回鏈表中環的起點，沒有返回NULL。

不能修改鏈表，能在不使用額外空間情況下解決嗎？

首先如何確認鏈表有環？有環代表經過一段後移回到環的起點。

如果是循環鏈表，那麼很簡單，只要用一個指針向後移動，如果回到起點，那麼就是環。但是問題是我們不知道環的起點在哪，一個粗暴的解法就是從頭開始對每個節點都進行一次上述步驟，但是問題在於如果當前節點不是環的起點，那就無法結束。另外的想法就是藉助外部空間，如果我們建立一個記錄本，對每個節點記錄所指向的節點，那麼在一定時間內的確可以發現環的起點，當然這是一個解法。

但是如果不能藉助空間呢？那就必須出現起點和終點的記錄，試想如果我們使用兩個指針，一個快，一個慢，快的一次走兩步，慢的一次走一步，他們會相遇嗎？考慮最簡單的一個環的情況，如果我們將環展開，也就是說在環內走一圈就相當於在直線上展開那段距離：

那麼環外距離設為s，慢指針走過的距離設為n，則快指針走過的距離就為2n：

指針間距離n就是走過的整數個環的距離，說明肯定是可以相遇的。

那麼如果將環的起點返回呢？圖中我們可以看到起點不是相遇的位置，但是我們已經有了起點的信息，為什麼呢？

n是整數個環的距離，那麼慢指針此時與環起點的距離是n-s，如果再前進s步，就回到了環的起點！那怎麼走s步呢，我們不知道s，我們只需要讓另外的頭指針與慢指針一起每次走一步，剛好s步的時候再次和慢指針相遇！！！此時就是環起點位置了！

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ListNode *detectCycle(ListNode *head) { if (!head || !head->next) { return NULL; } ListNode* slow = head; ListNode* fast = head; do { if (!fast->next) { return NULL; } slow = slow->next; fast = fast->next->next; } while (fast && slow != fast); if (!fast) { return NULL; } // 第二個循環 fast = head; while (slow != fast) { slow = slow->next; fast = fast->next; } return slow;}

好的我們已經很好的理解了演算法，提醒下我在圖中簡化了情況：

多個環怎麼辦？

因為沿著頭節點走只會有一條路徑，因此我們肯定會找到確定的環，那些問題的結果也是退化為這裡的模型，當然這裡沒法找多個環的起點。

慢指針不一定是在第一個環停下的！

圖中我把慢指針停在了第一個環，為了便於畫圖，當然可能是在後面的環相遇的。