判斷連結清單中是否存在環的方法及證明

一、判斷連結清單中是否存在環的方法及證明

首先說明一點就是如果鍊中存在環，可能整個鍊是一個環，也可能是該連結清單的後面一部分形成了環。如何判斷連結清單中是否存在環，經典的判斷方法就是利用兩個指向連結清單頭節點的指針，同時移動，兩個指針每次移動的節點數是不一樣的，如果存在環，那麼這兩個指針随着移動次數的增加，肯定會某個節點相遇，否則移動快的指針會到率先達連結清單末尾，即不存在環。

有沒有同學會疑惑：如果存在環，這兩個移動速度不同的指針一定會相遇嗎，兩個指針速度值設定為多少合适呢？下面我們來證明一下：如果存在環，不管這兩個指針的移動速度為何，隻要速度不相同，同時移動若幹次後，這兩個指針肯定會相遇。證明過程如下：

（1）設兩個指針為P1、P2，P1的移動速度為每次移動m個節點，P2的移動速度為每次移動n個節點，0 < m < n。P1和P2初始都指向連結清單頭節點。另設連結清單中環中的節點為L1(L1 >= 2)，連結清單剩餘節點個數為L2（L2 >= 0）。

（2）我們利用假設法來證明，即假設會相遇，那麼接下來我們要做的就是能否來找到一個次數K，這個K使下面兩個條件a和b同時成立

a：(L2 + n*K) - (L2 + m*K) = h*L1 => K * (n - m) = h * L1 => h = K*(n-m)/L1（h為不小于1的整數，代表P2節點比P1節點在環中多走的圈數）。如果相遇了，那麼P2節點肯定比P1節點在環中多走了若幹圈，是以推出這個等式成立；如果這個等式成立，也能表示P1和P2肯定能同時走到同一個節點上。

b：m*K >= L2 => K >= L2/m,這個條件之是以存在，是因為P1和P2肯定是在環内相遇，環外由于速度不同，是不可能相遇的，那麼P1肯定進入環内了,那麼環外的節點肯定都經曆了。

（3）在m、n、L2、L1給定的條件下，不管這四個變量的值為多少，我們都能找到符合a和b的一個最小整數，就是我們要找的次數K。比如m = 2，n= 3，L1 = 4，L2 = 3，我們要找的K滿足的條件是K/4為不小于1的整數，并且K >= 1.5，可得滿足條件的最小整數為4，即同時移動4次，P1和P2會相遇。為了便于了解，我們以此為例，畫圖說明一下移動過程，如下圖所示：

綜上可知：如果連結清單中存在環，那麼兩個指針初始指向位置均為頭節點，并且兩個指針移動速度隻要不同并且均大于0，那麼同時移動若幹次後，這兩個指針肯定能夠相遇。如果這樣兩個指針能夠相遇，也說明連結清單中肯定存在環。

時間複雜度分析：設連結清單的長度為L，上述算法的時間複雜度為O(L)。因為該問題涉及到環以及兩個指針追逐的問題，最終的移動次數并不能很直覺的了解到，有些同學可能會有困惑為什麼是O(L)，有沒有可能比L大甚至大很多的情況呢？答案是沒有，移動次數不可能超過L，下面我們來分析證明一下：

有上面可知最終的移動次數K滿足兩個條件

(1)  h = (n-m)/L1 * K 

(2) K >= L2/m;

我們先考慮最壞情況下的移動次數，m=1時，條件2所要求的K的最小取值範圍是最大的，即K >= L2.。我們再對條件1的等式進一步化簡：h = t/s*K，其中t/s是(n-m)/L的最簡公約式，則1 <= s <= L1。如果s >= L2，那麼K = s即可滿足條件，那麼K <= L1 <= L；如果s < L2，那麼K = （u + 1）*sj即可，u為不超過L2/s的最大整數，那麼K = (us + s)  <= (L2 + s) <= (L2 + L1) = L。上面我們讨論的是最壞情況即m = 1的情況，K的取之仍會不超過L，那麼可知其他情況下，K的取值也定會不超過L，是以算法時間複雜度是O(L)。

二、問題升華：如果連結清單中存在環，那麼如何定位到連結清單中形成環的頭節點呢？

該問題的算法是基于問題一的，但是對兩指針的移動速度有了一個限制，就是兩指針速度最好相差1，即n-m=1，兩個指針相遇之後，我們隻需把P1初始化為頭節點，P2的位置保持不變，然後兩指針同時移動且每次均移動一個節點，那麼這兩個指針會再次相遇并且相遇時所處的節點就是環的頭節點。注意，該問題的解法中有兩次相遇，第一次是為了判斷存在環，第二次是為了定位環的頭節點。

證明過程：我們設兩指針第一次相遇的時候，指針P1在環内所走的圈數是q1，指針P2在環内所走的圈數是q2，另設第一次相遇所處的節點位置離環的頭節點的距離為d，那麼可得到下面兩個等式：

m*K = L2 + q1*L1 + d;

n*K = L2 + q2*L1 +d;

推導出n*(L2 + q1*L1 + d) = m*(L2 + q2*L1 +d) => d = (m*q2-n*q1)/(n-m)*L1 - L2，看到這個等式，我們設想，如果(m*q2-n*q1)/(n-m)為整數，那麼如果P2再走L2步，剛好可以走到環的頭節點，而把P1初始化為連結清單的頭節點，那麼P1走L2步，也能剛好走到環的頭節點。如何能讓(m*q2-n*q1)/(n-m)為總是為整數呢，那就是讓n-m=1。

是以可得結論，如果想找到連結清單中環的頭節點，則使用兩個移動速度相差1的指針，先讓它們相遇，然後在相遇的節點處，一個指針指向位置保持不變，另一個指針初始化為連結清單的頭節點，繼續讓他們同時移動，并且每次移動一個節點，那麼它們定會在環的頭節點相遇。

閑來無事，對上述兩個問題的解法加以證明，也好做到用起來心中無疑慮。