typedef struct LNode
{
int data;
LNode *next;
}LNode ;
typedef LNode* LinkList;
//單鏈表有環返回true 否則返回false
bool is_looplist(LNode *head)
{
LNode *fast,*slow;
if (head == NULL || head->next == NULL)
{
return false;
}
slow = head;fast = head->next;
while(true)
{
if(!fast || !fast->next)
return false;
//為了防止fast跨過slow的情況,在每次判斷的時候比較當前節點和下一節點
else if (fast == slow || fast->next == slow)
return true;
else
{
slow = slow->next;//一次跳一步
fast = fast->next->next;//一次跳兩步
}
}
}如果要返回環的入口節點
一種效率比較低的方法是
一個指針p1從表頭開始,指針p2 初始化為判環時找到的指針,p1每前進一步,由p2遍歷一次環中各結點,遍歷過程中每次都要判斷p1是否p2
當p2 == fast時候,p1 = p1.next,繼續循環。這樣肯定能找到入口,但是效率為O(n^2)




