判斷單鏈表是否存在環(huán)，判斷兩個(gè)鏈表是否相交問題詳解
摘要: 有一個(gè)單鏈表，其中可能有一個(gè)環(huán)，也就是某個(gè)節(jié)點(diǎn)的next指向的是鏈表中在它之前的節(jié)點(diǎn)，這樣在鏈表的尾部形成一環(huán)。
問題：
1、如何判斷一個(gè)鏈表是不是這類鏈表？
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，則為無環(huán)鏈表)程序如下：
bool IsExitsLoop(slist *head)
{
slist *slow = head, *fast = head;
while ( fast && fast->next )
{
slow = slow->next;
fast = fast->next->next;
閱讀全文
posted @
2008-04-17 10:21 胡滿超 閱讀(34802) |
評論 (23) 編輯