如何判断一个单链表是有环的？（注意不能用标志位 最多只能用两个额外指针）
指针,标志,两个
已帮助 人
-
正确答案：
struct node { char val; node* next;}
bool check(const node* head) {} //return false : 无
环；true: 有环
一种O（n）的办法就是（搞两个指针，一个每次
递增一步，一个每次递增两步，如果有环的话两者
必然重合，反之亦然）：
bool check(const node* head)
{
if(head==NULL) return false;
node *low=head, *fast=head->next;
while(fast!=NULL && fast->next!=NULL)
{
low=low->next;
fast=fast->next->next;
if(low==fast) return true;
}
return false;
}