轉(zhuǎn)自：http://www.cppblog.com/humanchao/archive/2008/04/17/47357.html

有一個單鏈表，其中可能有一個環(huán)，也就是某個節(jié)點的next指向的是鏈表中在它之前的節(jié)點，這樣在鏈表的尾部形成一環(huán)。

問題：

1、如何判斷一個鏈表是不是這類鏈表？
2、如果鏈表為存在環(huán)，如何找到環(huán)的入口點？

解答：

一、判斷鏈表是否存在環(huán)，辦法為：

設置兩個指針(fast, slow)，初始值都指向頭，slow每次前進一步，fast每次前進二步，如果鏈表存在環(huán)，則fast必定先進入環(huán)，而slow后進入環(huán)，兩個指針必定相遇。(當然，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);
}

因為fast是slow的兩倍，所以當slow正好轉(zhuǎn)完一圈的時候，則fast也轉(zhuǎn)完兩圈，所以在slow的第一圈內(nèi)，fast一定能趕上slow

二、找到環(huán)的入口點

當fast若與slow相遇時，slow肯定沒有走遍歷完鏈表，而fast已經(jīng)在環(huán)內(nèi)循環(huán)了n圈(1<=n)。假設slow走了s步，則fast走了2s步（fast步數(shù)還等于s 加上在環(huán)上多轉(zhuǎn)的n圈），設環(huán)長為r，則：

2s = s + nr
s= nr

設整個鏈表長L，入口環(huán)與相遇點距離為x，起點到環(huá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)為相遇點到環(huán)入口點的距離，由此可知，從鏈表頭到環(huán)入口點等于(n-1)循環(huán)內(nèi)環(huán)+相遇點到環(huán)入口點，于是我們從鏈表頭、與相遇點分別設一個指針，每次各走一步，兩個指針必定相遇，且相遇第一點為環(huá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;
}

擴展問題：

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

比較好的方法有兩個：

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

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

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

總結(jié)

以上是生活随笔為你收集整理的单链表相交和环的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。