如何判断链表是否存在循环

如何判断链表是否存在循环

社区

C语言 帖子详情 如何判断链表是否存在循环 reinhardai 2005-10-11 10:25:41 我写了一个程序,思想是两个指针,一个指向第一个,一个指向第三个,判断它们是否相

等,如果等,就是循环,如果不等,第一前进一个,第二个前进两个,继续判断,直至相

等或者一个遇到null为止,感觉上好像有点问题

int is_circle(struct list *head)

{

if(head==null&&head->next==null) return 0;

list *p=head;

list *q=head->next;

if(q->next==null) return 0;

q=q->next;

while(p!=null&&q!=null)

{

if(p==q)

return 1;

else

{

p=p->next;

q=q->next;

if(q->next==null) return 0;

q=q->next;

}

}

return 0;

}

...全文

348 11 打赏 收藏 如何判断链表是否存在循环 我写了一个程序,思想是两个指针,一个指向第一个,一个指向第三个,判断它们是否相 等,如果等,就是循环,如果不等,第一前进一个,第二个前进两个,继续判断,直至相 等或者一个遇到null为止,感觉上好像有点问题 int is_circle(struct list *head) { if(head==null&&head->next==null) return 0; list *p=head; list *q=head->next; if(q->next==null) return 0; q=q->n 复制链接

扫一扫 分享 转发到动态 举报 AI 作业

写回复 配置赞助广告取 消

确 定

用AI写文章 11 条回复 切换为时间正序 请发表友善的回复… 发表回复 打赏红包 需支付: 0.00 元 取 消 确 定 iwdc 2005-10-18 打赏举报 回复 建议 Cnwanglin(林) 的程序里面开头部分

//判断节点的个数为0或者1个的时候,不可能存在循环

if(head==null&&head->next==null) return 0;

“&&”改成“||” skg55 2005-10-14 打赏举报 回复 给还不明白的兄弟点提示,如果有环,那就相当于一个操场,这时p在起点,而q在p前面2个单位,因为操场是圆的,所以也可以说q在p后面n个单位(n=操场周长-2),然后pq一起往前走,p每次走1个单位,q每次走2个单位,好了,这就变成了高中时候物理的追赶问题了,他们的距离差为n个单位,他们的速度差为2-1=1个单位,那么只要有足够的时间,哪怕操场(即这个环)再大也一定能追上,也就是说总有一个时刻p=q!

希望对兄弟们有帮助^_^ reinhardai 2005-10-11 打赏举报 回复 这个考虑了亚,p=head了,然后q=head->next,由于head->!=null,q=head->next->next,最后q=head了,判断了 pomelowu 2005-10-11 打赏举报 回复 你这样会漏掉很多可能的循环方式。

比如

head == 0x00000001;

head->next == head;

你的程序就无法检测到。

可以沿head往后,把所有next保存到一个数组中,然后没拿到一个next,就与这个数组的元素相比较 reinhardai 2005-10-11 打赏举报 回复 在k()的程序里面

else

{

p=p->next;

q=q->next;

}

q每次前进一个,这样不一定可以检测循环

我说话有的时候太简洁了

谢谢Cnwanglin(林) 的注释,呵呵 Cnwanglin 2005-10-11 打赏举报 回复 我加下注释,请问问题:“后面的前进一个不行”是什么意思

==================================================

/*

*功能:判断链表中是否存在节点

*名称:is_circle(struct list *)

*传入参数:struct list* 链表的首地址

*返回值:int (1)为0,链表中无循环

(2) 为1,链表中有循环

*/

int is_circle(struct list *head)

{

//判断节点的个数为0或者1个的时候,不可能存在循环

if(head==null&&head->next==null) return 0;

//定义指针p,q,分别指向head; head->next;

list *p=head;

list *q=head->next;

//判断节点的个数为2个的时候,如果不是循环,退出;

if(q->next==null) return 0;

q=q->next;

//循环判断

while(p!=null&&q!=null)

{

if(p==q)

//存在循环,退出

return 1;

else

{

p=p->next;

q=q->next;

//指针q的STEP为2,要加上这句判断;(q + 1)是否为链表的终点

if(q->next==null) return 0;

//(q + 2)

q=q->next;

}

}

return 0;

}

reinhardai 2005-10-11 打赏举报 回复 这个有问题,后面的前进一个不行 K 2005-10-11 打赏举报 回复 int is_circle(struct list *head)

{

if(head==null&&head->next==null) return 0;

list *p=head;

list *q=head->next;

if(q->next==null) return 0;

q=q->next;

while(p!=null&&q!=null)

{

if(p==q)

return 1;

else

{

p=p->next;

q=q->next;

}

}

return 0;

}

reinhardai 2005-10-11 打赏举报 回复 最前面的判断是防止出现q=null后还继续前进,即没有循环,而且就一个或者两个节点的情况,

使用时没有出现什么问题,就是感觉上有点不是太对,说不上来的感觉,呵呵

就是请大家看看有没有问题,如果有,讨论一下 pomelowu 2005-10-11 打赏举报 回复 我弄错了。那还有什么问题 Cnwanglin 2005-10-11 打赏举报 回复 判断的方法应该没错的, 如果STEP 不同,那么两个指针指向同一地址的时候,表明该链表内有循环。

具体出了什么问题了么?

==============================================

回复人: pomelowu(羽战士) ( ) 信誉:99 2005-10-11 11:20:00 得分: 0

提到的方法中:说的是当链表的节点个数小于3个的时候,这种情况: A <-> B 两个节点的循环,

但是在您的程序中:

list *p=head;

list *q=head->next;

if(q->next==null) return 0;

这里已经作了判断

所以,如果使用起来出现什么问题

麻烦您贴上来,关注;

==================================================

不对的地方还请多指点! 判断单链表中是否存在环 笔试时,常见的题型。判断单链表中是否存在环 用C++实现的循环链表 这是一个单循环链表,具备基本的操作,在普通链表的基础上,实现了定长循环链表的循环输入,判断链表是否有环等较为特殊的操作。增删改查自然也有。 带头结点和不带头结点的循环链表 这学期学数据结构,写了带头结点和不带头结点的循环链表,供其他在校学生参考学习,体会在链表中带头结点和不带头结点的差别 python单向循环链表原理与实现方法示例 本文实例讲述了python单向循环链表原理与实现方法。分享给大家供大家参考,具体如下:

单向循环链表

单链表的一个变形是单向循环链表,链表中最后一个节点的next域不再为None,而是指向链表的头节点。

操作

is_empty() 判断链表是否为空

length() 返回链表的长度

travel() 遍历

add(item) 在头部添加一个节点

append(item) 在尾部添加一个节点

insert(pos, item) 在指定位置pos添加节点

remove(item) 删除一个节点

search(item) 查找节点是否存在

实现

# -*- cod

C语言

70,020

社区成员

243,267

社区内容

发帖 与我相关 我的任务 C语言 C语言相关问题讨论 复制链接

扫一扫 分享 确定 社区描述 C语言相关问题讨论 社区管理员

加入社区

获取链接或二维码

近7日

近30日

至今

加载中

查看更多榜单

社区公告

暂无公告 试试用AI创作助手写篇文章吧

+ 用AI写文章

相关推荐

摩拜单车获得520贴纸要骑行多久 怎么看自己有多少贴纸
《Bloodborne》支线攻略(包含第三脐带收集方法)
365体育投注英超

《Bloodborne》支线攻略(包含第三脐带收集方法)

📅 06-27 👁️ 4116
掌握菊花的扦插祕訣,輕鬆培育新盆栽,附詳細操作指南