轉(zhuǎn)自：http://m.shnenglu.com/humanchao/archive/2008/04/17/47357.html
有一個(gè)單鏈表，其中可能有一個(gè)環(huán)，也就是某個(gè)節(jié)點(diǎn)的next指向的是鏈表中在它之前的節(jié)點(diǎn)，這樣在鏈表的尾部形成一環(huán)。
問(wèn)題：
1、如何判斷一個(gè)鏈表是不是這類(lèi)鏈表？
2、如果鏈表為存在環(huán)，如何找到環(huán)的入口點(diǎn)？
解答：
一、判斷鏈表是否存在環(huán)，辦法為：
設(shè)置兩個(gè)指針(fast, slow)，初始值都指向頭，slow每次前進(jìn)一步，fast每次前進(jìn)二步，如果鏈表存在環(huán)，則fast必定先進(jìn)入環(huán)，而slow后進(jìn)入環(huán)，兩個(gè)指針必定相遇。(當(dāng)然，fast先行頭到尾部為NULL，則為無(wú)環(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相遇時(shí)，slow肯定沒(méi)有走遍歷完鏈表，而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)長(zhǎng)為r，則：
2s = s + nr
s= nr
設(shè)整個(gè)鏈表長(zhǎng)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è)一個(gè)指針，每次各走一步，兩個(gè)指針必定相遇，且相遇第一點(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;
}
擴(kuò)展問(wèn)題：
判斷兩個(gè)單鏈表是否相交，如果相交，給出相交的第一個(gè)點(diǎn)（兩個(gè)鏈表都不存在環(huán)）。
比較好的方法有兩個(gè)：
一、將其中一個(gè)鏈表首尾相連，檢測(cè)另外一個(gè)鏈表是否存在環(huán)，如果存在，則兩個(gè)鏈表相交，而檢測(cè)出來(lái)的依賴(lài)環(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)。
posted on 2012-04-09 16:56
王海光 閱讀(770)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
算法