題目：
給定一個單連結清單，隻給出頭指針head：
1、如何判斷是否存在環？
2、如何知道環的長度？
3、如何找出環的連接配接點在哪裡？
4、帶環連結清單的長度是多少？
解法：
1、對于問題1，使用追趕的方法，設定兩個指針slow、fast，從頭指針開始，每次分别前進1步、2步。如存在環，則兩者相遇；如不存在環，fast遇到NULL退出。
解析：
如果以其它速度前進是否可以呢？ 下面我主要讨論這個問題。 假設p和q分别以速度為v1和v2前進。如果有環，設指針p和q第一次進入環時，他們相對于環中第一個節點的偏移位址分别為a和b（可以把偏移位址了解為節點個數）。如上圖。 這樣，可以看出，連結清單有環的充要條件就是某一次循環時，指針p和q的值相等，就是它們相對環中首節點的偏移量相等。 我們設環中的結點個數為n,程式循環了m次。 由此可以有下面等式成立：(mod(n)即對n取餘) (a+m*v1)mod(n) = (b+m*v2) mod(n) 設等式左邊mod(n)的最大整數為k1，等式右邊mod(n)的最大整數為k2，則 (a+m*v1)-k1*n = (b+m*v2)-k2*n 整理以上等式： m= |((k2-k1)*n+a-b)/( v2-v1)| ① 如果是等式①成立，就要使循環次數m為一整數。顯然如果v2-v1為1，則等式成立。 這樣p和q分别以速度為v1和v2且|v2-v1|為1時，按以上算法就可找對外連結表中是否有環。
也可以這麼了解：
假定單連結清單的長度為n，并且該單連結清單是環狀的，那麼第i次疊代時，p指向元素i mod n，q指向2i mod n。是以當i≡2i(mod n)時，p與q相遇。而i≡2i(mod n) =>（推出） (2i - i) mod n = 0 => i mod n = 0 => 當i=n時，p與q相遇。
這裡一個簡單的了解是，p和q同時在操場跑步，其中q的速度是p的兩倍，當他們兩個同時出發時，p跑一圈到達起點，而q此時也剛 好跑完兩圈到達起點。
那麼當p與q起點不同呢？假定第i次疊代時p指向元素i mod n，q指向k+2i mod n，其中0<k<n。那麼i≡(2i+k)(mod n) => (i+k) mod n = 0=> 當i=n-k時，p與q相遇。
2、對于問題2，記錄下問題1的碰撞點p，slow、fast從該點開始，再次碰撞所走過的操作數就是環的長度s。
3、問題3：有定理：碰撞點p到連接配接點的距離=頭指針到連接配接點的距離，是以，分别從碰撞點、頭指針開始走，相遇的那個點就是連接配接點。(證明在後面附注)
4、問題3中已經求出連接配接點距離頭指針的長度，加上問題2中求出的環的長度，二者之和就是帶環單連結清單的長度
判斷是否存在環的程式：
[cpp] view plain copy
- bool IsExitsLoop(slist *head)
- {
- slist *slow = head, *fast = head;
- while ( fast && fast->next )
- {
- slow = slow->next;
- fast = fast->next->next;
- if ( slow == fast ) break;
- }
- return !(fast == NULL || fast->next == NULL);
- }
尋找環連接配接點（入口點）的程式：
[cpp] view plain copy
- slist* FindLoopPort(slist *head)
- {
- slist *slow = head, *fast = head;
- while ( fast && fast->next )
- {
- slow = slow->next;
- fast = fast->next->next;
- if ( slow == fast ) break;
- }
- if (fast == NULL || fast->next == NULL)
- return NULL;
- slow = head;
- while (slow != fast)
- {
- slow = slow->next;
- fast = fast->next;
- }
- return slow;
- }
亦可以用類似與hash表的方法，即設立一個數組，将連結清單結點中的值做數組下标，當指派沖突時就是環的接入點
證明題：
對于一個順時針的環，有P,Q兩點，且兩點相距為N,同時，P每向前移動一步，Q就向前以東兩步，已知環的周長是L,問P,Q兩點相遇在哪點上？如下圖所示：P點是環的入口點
假設P,Q兩點相遇時，P點移動的距離是X,則有以下等式：
X-N = 2*X - L;
=>X= L-N
那麼我可以從上圖看到相遇點離入口點的距離為：L-(L-N)=N
綜上所述：
假設單連結清單的總長度為L，頭結點到環入口的距離為a，環入口到快慢指針相遇的結點距離為x，環的長度為r，慢指針總共走了s步，則快指針走了2s步。另外，快指針要追上慢指針的話快指針至少要在環裡面轉了一圈多(假設轉了n圈加x的距離)，得到以下關系：
s = a + x
2s = a + nr + x
=>a + x = nr
=>a = nr - x
由上式可知：若在頭結點和相遇結點分别設一指針，同步(單步)前進，則最後一定相遇在環入口結點
通過上面的證明題發現數學知識在程式設計世界中真的很重要呀~~
也可以這麼了解：
假設連結清單長度是L，前半部分長度為k-1，那麼第一個再環裡的節點是k，環的長度是 n， 那麼當q=2p時， 什麼時候第一次相交呢？當q指針走到第k個節點時，q指針已經在環的第 k mod n 的位置。即p和q 相差k個元素，從不同的起點開始，則相交的位置為 n-k, 則有了下面的圖：
從圖上可以明顯看到，當p從交點的位置（n-k) ,向前周遊k個節點就到到達環的第一個幾點，節點k.
算法就很簡單： 一個指針從p和q 中的第一次相交的位置起（n-k)，另外一個指針從連結清單頭開始周遊，其交點就是連結清單中第一個在環裡的交點。
總結：我們看到這裡面有一個核心的地方就是第一個問題，判斷有沒有環的情況，采用了兩個指針：快指針和慢指針，這個在處理一些連結清單的問題中尤其重要，比如下面的兩道關于連結清單的題目：
第一題：已知單連結清單的頭指針，查找到倒數第K個節點
這道題的通俗的解法就是先周遊一邊連結清單，得到連結清單的長度N,然後再從頭開始周遊N-K個節點即可
但是現在如果要求隻周遊一遍連結清單的話，該怎麼操作呢？
這時候就可以借助快指針和慢指針了
我們定義一個快指針P和慢指針Q,先讓P指針走到K個節點位置，然後Q指針從頭指針開始和P一起移動，當P移動到尾部的時候，那麼此時Q節點所在的位置就是倒數第K個節點。
第二題：已知單連結清單的頭結點，查找到連結清單的中間節點
這道題的通俗的解法和上面的方法一樣，就是先周遊一邊連結清單，得到連結清單的長度N，然後再次周遊N/2個節點即可
但是現在同樣的如果要求之周遊一邊連結清單的話，該怎麼操作呢？
這時候我們同樣可以借助快指針和慢指針了
我們定義一個快指針P和慢指針Q,P和Q同時從頭指針出發，快指針P每次移動兩步，慢指針每次移動一步，當快指針P到尾部的時候，慢指針Q所在的位置就是中間節點的位置。
通過上面的兩道題目我們可以看到快慢指針的在解決單連結清單的相關問題上還是很有用的~~
下面在來看一下還有一個技巧就是在解決第二道題目的時候，那個求環的入口節點，這個當時真的是沒有任何頭緒，是以這時候就要求我們又很好的數學功底了，能夠發現相關的規律，然後總結出定理，這樣就可以将問題簡化了。