社区
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写文章