算法-在单向链表中,如何检查是否有环的情况

WordPress 开发 WordPress 开发 主题:1098 回复:2322

算法-在单向链表中,如何检查是否有环的情况

偏爱自由 发布于 2017-05-12 字数 114 浏览 1016 回复 3

在单向链表中,如何检查是否有环的情况?
例如:
1->2->3->4->5->3

语言不限!

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

支持 Markdown 语法,需要帮助?

评论(3

泛泛之交 2017-09-14 3 楼

最简单的就是链表的点加多一个标志位,访问到就置为1.每次访问到一个点先判断它的标志位是否为1,在遍历结束前如果能找到标志为1的点,那么就存在环了

偏爱自由 2017-08-28 2 楼

设置两个指针(fast, slow),初始值都指向头,slow每次前进一步,fast每次前进二步,如果链表存在环,则fast必定先进入环,而slow后进入环,两个指针必定相遇。(当然,fast先行头到尾部为NULL,则为无环链表)

int is_link_list_cicled(Node head)
{
Node
p = head, *q = head;
while(p && q)
{
if(p == q)
return 1;
p = p-> next;
q = q-> next;
if(!q)
return 0;
q = q-> next;
}
return 0;
}

如果链表有环,不妨假设其环长度为M(>=2)。
p指针首次到达交点(N0)时,q指针已经进入环。
设p=0;q=q-p;
再进过i(i>=0)步后,p=(p+i)%m;q=(q+2i)%m;
则必存在一个i使得(p+i)%m = (q+2
i)%m。(p,q 都为常数)。

清晨说ぺ晚安 2017-06-17 1 楼

int circle(NODE list){
if( list == NULL || list->next == NULL)//无接点或者只有一个节点且不形成自环
return false;
if( list == list->next)//自环
return true;
NODE
slow = list;
NODE *fast = list->next;
while( slow != fast && fast->next !=NULL && fast->next->next != NULL ){
slow = slow->next;
fast = fast->next->next;
}
if(slow == fast)
return true;
return false;
}