那么上一題我們已經知道了雙指針的變法以及拓展的用法，那么這里我們直接難度升級。
想回去復習的這里放個鏈接：鏈表的面試題8之環形鏈表-CSDN博客
題目鏈接：142. 環形鏈表 II - 力扣（LeetCode）
?我們來看這道題目主要想讓我們干什么，上一題是讓我們去判斷是否為環形鏈表，而這一題是直接告訴你這就是一個環形鏈表，讓你自己去探尋環形鏈表各節點的關系，用地址來判斷這個節點是否是第一個成環的節點。
當然這一題還是用雙指針的解法，至于為什么很簡單，單指針解決不了這個問題唄。我們上一題探討過快慢指針的步調的大小，涉及快慢指針的算法題中，通常習慣使用快指針每次走兩步，慢指針走一步的方式。
這里我們需要判斷的難點是什么？？
我們之前用到的快慢指針都是通過他們的距離差讓這兩個指針相遇來得出這個是環形鏈表，但是這里我們相遇的點萬一不是第一個點呢？？那么我們的判斷不就成了無效判定了嗎？所以我們篤定一點，這道題像上一道題那樣的關系判斷是不可取的，我們應該找其他的關系，使得讓兩個節點一定在第一個成環的節點相遇。
那我們直接來畫圖看一下：
這里我們設從頭節點到入環的第一個節點的距離為a，設環長為c。
再設相遇的時候，慢指針走了b步，那么這里快指針就走了2b步。
再設快指針比慢指針多走了k圈環，那么我們就能得到2b-b=kc，即b=kc。
再看我們的慢指針，從頭節點開始，到相遇點走了b-a步，也就是（kc-a）步。
這也就是說，從相遇點開始，再走a步，就會到達我們的入環點。
為什么？
因為環長就是c，看圖中的箭頭，一根箭頭代表一個長度。所以再走a步，也就是說(kc-a+a)=kc步
也就是在入環口處。那么哪里還有a步的地方呢？
我再往圖里一看，那就是頭節點處，所以我如果讓指針從頭節點和相遇點處分別開始移動，那么兩個人步伐都為1的情況下肯定會在入環口處相遇。
結論就是：讓一個指針從鏈表起始位置開始遍歷鏈表，同時讓一個指針從判環時相遇點的位置開始繞環運行，兩個指針都是每次均走一步，最終肯定會在入口點的位置相遇。
但要注意一點：指針從相遇點開始，移動 a 步后恰好走到入環口，但在這個過程中，可能會多次經過入環口。 因為環長和入環前的長度可能會有誤差。
struct ListNode* detectCycle(struct ListNode* head) {struct ListNode* slow = head;struct ListNode* fast = head;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;if (fast == slow) { // 相遇while (slow != head) { // 再走 a 步slow = slow->next;head = head->next;}return slow;}}return NULL;
}這里把代碼貼一下，整個思路是非常清晰的，效率也非常高。
時間復雜度：O(n)，其中 n 為鏈表的長度。
空間復雜度：O(1)，僅用到若干額外變量。
這里再帶大家注意兩點推導設條件的前提：1.慢指針在進入環之前，快指針就已經在環內至少走了n圈，而n至少為1。因為快指針至少要走一圈，才能與后進入的慢指針相遇。
2.慢指針進環之后，快指針肯定會在慢指針走一圈之內追上慢指針
因為：慢指針進環后，快慢指針之間的距離最多就是環的長度，而兩個指針在移動時，每次它們至今的距離都縮減一步，因此在慢指針移動一圈之前快指針肯定是可以追上慢指針的。
好了，這道題就講到這里
如果你覺得對你有幫助，可以點贊關注加收藏，感謝您的閱讀，我們下一篇文章再見。
一步步來，總會學會的，首先要懂思路，才能有東西寫。
