判斷單鏈表是否存在環，判斷兩個鏈表是否相交問題詳解
摘要: 有一個單鏈表，其中可能有一個環，也就是某個節點的next指向的是鏈表中在它之前的節點，這樣在鏈表的尾部形成一環。
問題：
1、如何判斷一個鏈表是不是這類鏈表？
2、如果鏈表為存在環，如果找到環的入口點？
解答：
一、判斷鏈表是否存在環，辦法為：
設置兩個指針(fast, slow)，初始值都指向頭，slow每次前進一步，fast每次前進二步，如果鏈表存在環，則fast必定先進入環，而slow后進入環，兩個指針必定相遇。(當然，fast先行頭到尾部為NULL，則為無環鏈表)程序如下：
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 胡滿超 閱讀(34851) |
評論 (23) 編輯