有一個單鏈表，其中可能有一個環(huán)，也就是某個節(jié)點(diǎn)的next指向的是鏈表中在它之前的節(jié)點(diǎn)，這樣在鏈表的尾部形成一環(huán)。1、如何判斷一個鏈表是不是這類鏈表？2、如果鏈表為存在環(huán)，如果找到環(huán)的入口點(diǎn)？擴(kuò)展：判斷兩個單鏈表是否相交，如果相交，給出相交的第一個點(diǎn)。
有一個單鏈表，其中可能有一個環(huán)，也就是某個節(jié)點(diǎn)的next指向的是鏈表中在它之前的節(jié)點(diǎn)，這樣在鏈表的尾部形成一環(huán)。
問題：
1、如何判斷一個鏈表是不是這類鏈表？
2、如果鏈表為存在環(huán)，如果找到環(huán)的入口點(diǎn)？
解答：
一、判斷鏈表是否存在環(huán)，辦法為：
設(shè)置兩個指針(fast, slow)，初始值都指向頭，slow每次前進(jìn)一步，fast每次前進(jìn)二步，如果鏈表存在環(huán)，則fast必定先進(jìn)入環(huán)，而slow后進(jìn)入環(huán)，兩個指針必定相遇。(當(dāng)然，fast先行頭到尾部為NULL，則為無環(huán)鏈表)程序如下：
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);
}
二、找到環(huán)的入口點(diǎn)
當(dāng)fast若與slow相遇時，slow肯定沒有走遍歷完鏈表，而fast已經(jīng)在環(huán)內(nèi)循環(huán)了n圈(1<=n)。假設(shè)slow走了s步，則fast走了2s步（fast步數(shù)還等于s 加上在環(huán)上多轉(zhuǎn)的n圈），設(shè)環(huán)長為r，則：
2s = s + nr
s= nr
設(shè)整個鏈表長L，入口環(huán)與相遇點(diǎn)距離為x，起點(diǎn)到環(huán)入口點(diǎn)的距離為a。
a + x = nr
a + x = (n – 1)r +r = (n-1)r + L - a
a = (n-1)r + (L – a – x)
(L – a – x)為相遇點(diǎn)到環(huán)入口點(diǎn)的距離，由此可知，從鏈表頭到環(huán)入口點(diǎn)等于(n-1)循環(huán)內(nèi)環(huán)+相遇點(diǎn)到環(huán)入口點(diǎn)，于是我們從鏈表頭、與相遇點(diǎn)分別設(shè)一個指針，每次各走一步，兩個指針必定相遇，且相遇第一點(diǎn)為環(huán)入口點(diǎn)。
程序描述如下：
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;
}
附一種易于理解的解釋：
一種O（n）的辦法就是（搞兩個指針，一個每次遞增一步，一個每次遞增兩步，如果有環(huán)的話兩者必然重合，反之亦然）：
關(guān)于這個解法最形象的比喻就是在操場當(dāng)中跑步，速度快的會把速度慢的扣圈
可以證明，p2追趕上p1的時候，p1一定還沒有走完一遍環(huán)路，p2也不會跨越p1多圈才追上
我們可以從p2和p1的位置差距來證明，p2一定會趕上p1但是不會跳過p1的
因?yàn)閜2每次走2步，而p1走一步，所以他們之間的差距是一步一步的縮小，4，3，2，1，0 到0的時候就重合了
根據(jù)這個方式，可以證明，p2每次走三步以上，并不總能加快檢測的速度，反而有可能判別不出有環(huán)
既然能夠判斷出是否是有環(huán)路，那改如何找到這個環(huán)路的入口呢？
解法如下： 當(dāng)p2按照每次2步，p1每次一步的方式走，發(fā)現(xiàn)p2和p1重合，確定了單向鏈表有環(huán)路了
接下來，讓p2回到鏈表的頭部，重新走，每次步長不是走2了，而是走1，那么當(dāng)p1和p2再次相遇的時候，就是環(huán)路的入口了。
這點(diǎn)可以證明的：
在p2和p1第一次相遇的時候，假定p1走了n步驟，環(huán)路的入口是在p步的時候經(jīng)過的，那么有
p1走的路徑： p+c ＝ n； c為p1和p2相交點(diǎn)，距離環(huán)路入口的距離
p2走的路徑： p+c+k*L = 2*n； L為環(huán)路的周長，k是整數(shù)
顯然，如果從p+c點(diǎn)開始，p1再走n步驟的話，還可以回到p+c這個點(diǎn)
同時p2從頭開始走的話，經(jīng)過n步，也會達(dá)到p+c這點(diǎn)
顯然在這個步驟當(dāng)中p1和p2只有前p步驟走的路徑不同，所以當(dāng)p1和p2再次重合的時候，必然是在鏈表的環(huán)路入口點(diǎn)上。
擴(kuò)展問題：
判斷兩個單鏈表是否相交，如果相交，給出相交的第一個點(diǎn)（兩個鏈表都不存在環(huán)）。
比較好的方法有兩個：
一、將其中一個鏈表首尾相連，檢測另外一個鏈表是否存在環(huán)，如果存在，則兩個鏈表相交，而檢測出來的依賴環(huán)入口即為相交的第一個點(diǎn)。
二、如果兩個鏈表相交，那個兩個鏈表從相交點(diǎn)到鏈表結(jié)束都是相同的節(jié)點(diǎn)，我們可以先遍歷一個鏈表，直到尾部，再遍歷另外一個鏈表，如果也可以走到同樣的結(jié)尾點(diǎn)，則兩個鏈表相交。
這時我們記下兩個鏈表length，再遍歷一次，長鏈表節(jié)點(diǎn)先出發(fā)前進(jìn)(lengthMax-lengthMin)步，之后兩個鏈表同時前進(jìn)，每次一步，相遇的第一點(diǎn)即為兩個鏈表相交的第一個點(diǎn)。
本文來自CSDN博客，轉(zhuǎn)載請標(biāo)明出處：http://blog.csdn.net/ssfp8762/archive/2009/07/08/4331419.aspx