1.帶環鏈表環開始的位置

（1）上面的這個測試用例使用的是包含了4個節點的帶環鏈表，我們要找的就是鏈表里面的環開始的節點的位置，拿這個測試用例而言，就是2這個節點，從這個節點開始，我們的鏈表就形成了一個環，我們要設計程序說明在普適的情況下面如何找到這個環開始位置的節點；

（2）我們這里的思路和之前的一個判斷鏈表是否存在環的相同的思路，我們的快指針肯定會先進入這個環，慢指針后進入這個環，當慢指針進入環的時候，我們的快指針肯定已經在環里面走了好幾圈了，我們假設慢指針一次走1步，快指針一次走2步，因為在這個過程中快指針每次都比慢指針多走一步，這個時候就一定是可以追上的；

（3）這個題目的解題方法，其實很簡單，但是你可能之前從來沒有考慮過這個問題，就是在環上面快慢指針相遇的地方我們設置為meet指針，在開始的位置，我們設置為head指針（注意這里的head指針是指的最開始的位置，下面的圖里面有表示），這個時候讓meet指針一次走一步，head指針一次走一步，這樣進行下去，他們相遇的地方，就是我們的題目里面要求的環的節點的初始位置；是不是很神奇，你可能會問，一定會在這個環的開始節點的位置相遇嗎，為什么會這么巧？對就是這樣的，一定會相遇的，我們是可以通過數學推演證明出來；

（4）我們利用的等量關系就是快指針走過的路程是慢指針的兩倍（這個并不是題目里面給出的，而是我們自己使用的），我們肯定是要在題目里面進行說明的，代碼表示就是fast=fast->next->next而慢指針則是slow=slow->next這樣表示的就是我們設置的慢指針一次走一步，快指針一次走兩步，我們分別表示出來再相遇的時候兩個指針各自走過的路程，利用快指針的路程==慢指針路程的兩倍進行列式計算，就可以得到一個等量關系，這個等量關系就可以說明meet和head指針相遇的位置就是我們要求的環的初始位置節點；

（5）這個路程的表示還是要使用到這個圖，L表示的是沒有進環之前走過的路程，N表示的就是慢指針進環到這兩個指針相遇走過的路程，我們還是假設這個環上面的節點元素的個數是C，慢指針走過的路程就是進環之前的L加上進環之后的N，快指針走過的路程就是進環之前的L加上（我們假設慢指針進環的時候，快指針已經走過了x圈），x*c還要加上N（這個地方可能比較難以理解，多去領悟吧）；

（6）利用快指針走的路程是慢指針2倍，就可以得到L=x*C-N這個表達式，當這個X=1的時候L==C-N那么就是說head指針進環之前的路程恰好可以讓meet指針走過C-N到達環開始節點位置在這個位置相遇，這個我們是可以很直觀的看出來的，但是x等于其他的不是一的數字的時候，好像就不是非常直觀了；

（7）我們對于原來的式子稍加化簡，得到L=（x-1)*C+C-N,這樣的話就是說當head指針走過L路程的時候,我們的meet指針走過x-1圈加上C-N這段路程，兩者還是會在這個環的初始位置相遇的。

（8）具體的代碼如下所示：

---

下面我們介紹這個題目的第二種方法，因為上面的這個方法雖然簡單，但是似乎不容易想到，因為如果我們是第一次做，我們是很難想到的，下面我們介紹的方法是基于我們之前的相交鏈表實現這個環的頭部位置節點的查找：

就是我們現在是相當于把這個環形從meet這個位置斷開，讓meet->next定義為newhead指針，這個時候meet后面已經沒有東西了，所以我們就要把這個meet->next置空；

這個時候就把這個找環開始位置節點的問題，轉換為求解兩個鏈表的相交節點，這個相交接點恰好是我們想要查找的環形鏈表的開始位置的節點（通過上面的圖片可以清晰的看出來）；這兩個鏈表一個就是原本的以head為節點的鏈表，另外的一個就是以我們自己重新進行定義的newhead作為頭部節點的鏈表，我們接下來的工作就是找這兩個鏈表的相交節點；

這個時候我們只需要對于這個程序稍加修改就可以了：修改的地方如下

（1）這個時候我們首先要把meet指針的next節點設置為newhead節點，讓后把這個meet->next置空（這個時候newhead是不會受到影響的，因為就相當于是把meet和后面節點的連接給切斷了）

（2）我們需要把之前的判斷相交節點代碼拷貝過來就可以了，然后在這個函數里面調用求解兩個鏈表相交節點的函數，我們需要傳遞的參數就是head和newhead這兩個作為參數；對于這個相交節點的問題，可以看我之前的這個博客，里面有詳細的介紹；

鏈表-----返回倒數第K個節點&&回文結構的判斷&&相交鏈表-CSDN博客https://blog.csdn.net/binhyun/article/details/138368598?spm=1001.2014.3001.5502（3）detectcycle函數里面，我們也是要進行相應的修改的，就是添加meet節點，定義newhead節點，然后把meet->next置空，最后把這個getintersrctionnode這個函數的返回值作為detectCycle函數的返回值就可以了。

?