abstract：判斷一個(gè)單向鏈表是否有環(huán)。（指向表頭結(jié)點(diǎn)的指針為head）方法一：（1）用兩個(gè)指針p1和p2分別指向表頭結(jié)點(diǎn)，即p1=p2=head（2）p1和p2分別采用1和2作為步長(zhǎng)遍歷該鏈表。（注意，p2應(yīng)該檢查當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)是否為NULL）（3）如果p1或者p2遇到了NULL，則證明該鏈表沒有環(huán)；若p1和p2在某時(shí)刻指向同一結(jié)點(diǎn)，則說明該鏈表有環(huán)。bool I***itsLoop(slis

判斷一個(gè)單向鏈表是否有環(huán)。（指向表頭結(jié)點(diǎn)的指針為head）

方法一：

（1）用兩個(gè)指針p1和p2分別指向表頭結(jié)點(diǎn)，即p1=p2=head

（2）p1和p2分別采用1和2作為步長(zhǎng)遍歷該鏈表。（注意，p2應(yīng)該檢查當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)是否為NULL）

（3）如果p1或者p2遇到了NULL，則證明該鏈表沒有環(huán)；若p1和p2在某時(shí)刻指向同一結(jié)點(diǎn)，則說明該鏈表有環(huán)。

bool I***itsLoop(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);
 
}

（4）若該表有環(huán)，

（a）設(shè)從表頭結(jié)點(diǎn)（包括）開始到環(huán)開始的結(jié)點(diǎn)（不包括）共 有l(wèi)1個(gè)結(jié)點(diǎn)；設(shè)從環(huán)開始結(jié)點(diǎn)（包括）到它們相遇的結(jié)點(diǎn)（不包括）共有l(wèi)2個(gè)結(jié)點(diǎn)；設(shè)從他們第一次相遇的結(jié)點(diǎn)開始（包括）到環(huán)開始結(jié)點(diǎn)（不包括）共有l(wèi)3個(gè)結(jié)點(diǎn)；設(shè)整個(gè)環(huán)共有c個(gè)結(jié)點(diǎn)。則有c=l2+l3，且l1+l2即為它們第一次相遇時(shí)，p1所遍歷的結(jié)點(diǎn)個(gè)數(shù)。

（b）當(dāng)它們第一次相遇時(shí)，固定p2，然后p1以1為步長(zhǎng)繼續(xù)遍歷此表，則他們?cè)俅蜗嘤鰰r(shí)，p1從上次相遇到這次相遇所經(jīng)過的總步長(zhǎng)即為環(huán)中結(jié)點(diǎn)的個(gè)數(shù)c。

（c）可以證明，當(dāng)他們第一次相遇時(shí)，p1不可能經(jīng)過環(huán)開始結(jié)點(diǎn)兩次，即不可能開始第二次遍歷環(huán)。設(shè)當(dāng)它們第一次相遇時(shí)，p2已經(jīng)把環(huán)遍歷了k遍(k>=1)則有：2(l1+l2) = l1+l2+kc，即l1+l2=kc

（d）l1+l2=kc=>l1=(k-1)c+l3

（e）固定p2在它們第一次相遇的結(jié)點(diǎn)，然后p1回到表頭，然后它們均以1為步長(zhǎng)遍歷鏈表，則它們第一次相遇時(shí)，即為環(huán)開始結(jié)點(diǎn)

方法二：

（a）p從表頭結(jié)點(diǎn)開始以1為步長(zhǎng)遍歷表，邊遍歷邊將表反向

（b）如果p遇到NULL，則說明表沒有環(huán)

（c）如果p最后等于head，則說明表有環(huán)，且記此時(shí)p所經(jīng)過的表的結(jié)點(diǎn)數(shù)為l（l=2l1+c，l1和c的定義見方法一）

（d）p再?gòu)谋眍^結(jié)點(diǎn)開始以1為步長(zhǎng)遍歷表，邊遍歷邊反向，當(dāng)遍歷到l/2時(shí)，停止，設(shè)兩個(gè)指針p1,p2均指向當(dāng)前結(jié)點(diǎn)，然后分別從兩個(gè)方向同時(shí)以1為步長(zhǎng)遍歷表（其中一個(gè)需要邊遍歷，邊反向鏈表），當(dāng)他們第相遇時(shí)，當(dāng)前結(jié)點(diǎn)即為環(huán)頭結(jié)點(diǎn)。且此時(shí)鏈表還原成原來的鏈表。

第三種方法（通過修改鏈表，最終可還原鏈表，且可去掉鏈表中的環(huán)）

或許可以再構(gòu)造了一個(gè)雙向鏈，但不存儲(chǔ)原來的數(shù)據(jù)而存儲(chǔ)節(jié)點(diǎn)指針：

typedef struct _PtrLinkNode
 
{
 
LinkNode* theNode;
 
struct _PtrLinkNode* prev;
 
struct _PtrLinkNode* next;
 
} PtrLinkNode;

然后在逆轉(zhuǎn)鏈表時(shí)把當(dāng)前節(jié)點(diǎn)指針加入到這個(gè)雙向鏈表中。當(dāng)逆轉(zhuǎn)結(jié)束時(shí)如果這個(gè)雙向鏈表的首尾的theNode不相等，則說明沒有死鏈，再逆轉(zhuǎn)回來就可以了；如果相等，則存在死鏈，再在這個(gè)雙向鏈表從兩端向中間進(jìn)行首尾比較，直到遇到不相等的兩個(gè)節(jié)點(diǎn)，這兩個(gè)節(jié)點(diǎn)形成的閉區(qū)間就是原來形成死鏈的節(jié)點(diǎn)，順序與現(xiàn)在在雙向鏈表中的順序相同。把雙向鏈表中位于這個(gè)區(qū)間之后的節(jié)點(diǎn)支掉，然后按雙向鏈表的順序重建鏈表就可以恢復(fù)出原來的鏈表并去除死鏈。時(shí)間復(fù)雜度和空間復(fù)雜度都是O(N)。

=====================================================

幾大派系的算法：

herryhuang(Herry) 派：

『圓子示蹤法』

每隔N個(gè)接點(diǎn)，插入一個(gè)示蹤圓子。如果找到示蹤圓子，那么就說明在該示蹤圓子之前存在死鏈，再怎么找到確卻的死鏈位置，有待探討；找完死鏈以后再把示蹤圓子刪除；

plainsong (短歌)派：

『查表法』

順著接點(diǎn)往下走，每走一個(gè)，查找記錄接點(diǎn)值是否存在，若存在，則有死鏈，且該接點(diǎn)就是死鏈位置，否則，記錄接點(diǎn)值。

老邁派：

『指針追趕法』

用兩個(gè)指針指向頭接點(diǎn)，然后順次遍歷連表，一個(gè)步進(jìn)１，一個(gè)步進(jìn)２，相遇且不是null，則有死鏈。相遇時(shí)都是null，則沒有。如果沒有死蓮，兩個(gè)指針是不會(huì)相遇的，除非在兩頭。

注：原子示蹤法中 示蹤原子的插入方法

 void* flags[MAX];

使用的時(shí)候這樣

比如原來是：

a1->next == a2

那么現(xiàn)在就是

a1->next == &flags[k];
flags[k] == a2;

這樣，拿到一個(gè)指針p后，只需要判斷

if（p >= flags && p <= &flags[MAX])

 即可判斷他是不是一個(gè)標(biāo)志節(jié)點(diǎn)，這個(gè)跟具體結(jié)構(gòu)沒有任何關(guān)系

方法時(shí)間空間復(fù)雜度：

再一個(gè)死循環(huán)里發(fā)現(xiàn)結(jié)論的最大時(shí)間為 K + N, (K 步長(zhǎng), N死循環(huán)長(zhǎng)度,M死循環(huán)位置)

而在這之前的復(fù)雜度為M, 所以復(fù)雜度最大為M + K + N, K越小時(shí)間越小

但是空間復(fù)雜度至少為(M + N)/K, 就要看怎么均勻這兩者.

而且如果要求對(duì)鏈表只能讀,也不能夠應(yīng)用

老邁的算法,時(shí)間復(fù)雜不如你的,但是它的空間復(fù)雜度幾乎為0

老邁的總結(jié)：

大家討論得差不多了吧，其實(shí)如果仔細(xì)看看上面的發(fā)言，就會(huì)發(fā)現(xiàn)后來的各位所討論的東西已經(jīng)有充分的討論了，其實(shí)如果僅僅要判斷鏈表是不是死鏈（這就是樓主的要求嘛），老邁的方法肯定比我的快，因?yàn)槲以L問的每一個(gè)節(jié)點(diǎn)至少要做三到四次比較（各位寫出代碼來接明白了），而老邁的只需要兩次。另外，我的方法申請(qǐng)空間肯定是要費(fèi)時(shí)間的。如高要找出那個(gè)出問題的節(jié)點(diǎn)，則我的方法就比較快了，因?yàn)閷⒉迦氲墓?jié)點(diǎn)放在線形表中。

如下，插入節(jié)點(diǎn)的步長(zhǎng)為Setp，存放這些插入的節(jié)點(diǎn)的線形表為p[]

如果在插入p[m]之后，碰到了曾經(jīng)插入的節(jié)點(diǎn)p[n]，則可以斷定，出問題的節(jié)點(diǎn)位于p[n-1]到p[m]之間，而它指向的位置，位于p[m – 1]到p[m]之間，這是個(gè)常量，最多再進(jìn)行2*Step*step次比較即可找到這個(gè)節(jié)點(diǎn)。這是個(gè)常數(shù)。

所以，我的方法的關(guān)鍵問題在于找到一個(gè)合理的方法存放線形表，剛才編了半天，很麻煩，呵呵，下午還有事，各位繼續(xù)發(fā)言，有時(shí)間的話寫一個(gè)出來大家看看，我先撤了。

============================================

三個(gè)派系的比較：

本帖的三大派別：

plainsong (短歌)派：

『查表法』

順著接點(diǎn)往下走，每走一個(gè)，查找記錄接點(diǎn)值是否存在，若存在，則有死鏈，且該接點(diǎn)就是死鏈位置，否則，記錄接點(diǎn)值。

—>這個(gè)似乎,雖然查找復(fù)雜度 最大僅 為 N,但是空間..汗汗..的確比較大

herryhuang(Herry) 派：

『圓子示蹤法』

每隔N個(gè)接點(diǎn)，插入一個(gè)示蹤圓子。如果找到示蹤圓子，那么就說明在該示蹤圓子之前存在死鏈，再怎么找到確卻的死鏈位置，有待探討；找完死鏈以后再把示蹤圓子刪除；

—>如果可以更改鏈表指針,個(gè)人認(rèn)為這個(gè)辦法是最好的,最大時(shí)間復(fù)雜度 N+K(K為步長(zhǎng)),如果K設(shè)置成一個(gè)比較合理的值,應(yīng)該能在時(shí)間和空間上都取得很好的效果(在前兩個(gè)K點(diǎn)前加兩個(gè)針指應(yīng)該可以把確定鏈表的范圍縮小到1K到2K之間吧

老邁派：

『指針追趕法』

用兩個(gè)指針指向頭接點(diǎn)，然后順次遍歷連表，一個(gè)步進(jìn)１，一個(gè)步進(jìn)２，相遇且不是null，則有死鏈。相遇時(shí)都是null，則沒有。如果沒有死蓮，兩個(gè)指針是不會(huì)相遇的，除非在兩頭。

–>這個(gè)辦法,有最小的空間占用吧,確定有死鏈最大應(yīng)該是2*N吧,確定位置應(yīng)該有相應(yīng)算法吧,估計(jì)是3N左右吧,如果是小型鏈表,這個(gè)辦法應(yīng)該比較好,但在巨型鏈表時(shí),這個(gè)從速度上而言,反而不如第二種辦法了吧.

擴(kuò)展問題：

判斷兩個(gè)單鏈表是否相交，如果相交，給出相交的第一個(gè)點(diǎn)（兩個(gè)鏈表都不存在環(huán)）。

比較好的方法有兩個(gè)：

一、將其中一個(gè)鏈表首尾相連，檢測(cè)另外一個(gè)鏈表是否存在環(huán)，如果存在，則兩個(gè)鏈表相交，而檢測(cè)出來的依賴環(huán)入口即為相交的第一個(gè)點(diǎn)。

二、如果兩個(gè)鏈表相交，那個(gè)兩個(gè)鏈表從相交點(diǎn)到鏈表結(jié)束都是相同的節(jié)點(diǎn)，我們可以先遍歷一個(gè)鏈表，直到尾部，再遍歷另外一個(gè)鏈表，如果也可以走到同樣的結(jié)尾點(diǎn)，則兩個(gè)鏈表相交。

這時(shí)我們記下兩個(gè)鏈表length，再遍歷一次，長(zhǎng)鏈表節(jié)點(diǎn)先出發(fā)前進(jìn)(lengthMax-lengthMin)步，之后兩個(gè)鏈表同時(shí)前進(jìn)，每次一步，相遇的第一點(diǎn)即為兩個(gè)鏈表相交的第一個(gè)點(diǎn)。