是技术,更是艺术
一心编程,就没有解决不了的问题
posts - 9, comments - 11, trackbacks - 0, articles - 0
导航
C++博客
首页
新随笔
联系
聚合
管理
<
2024年8月
>
日
一
二
三
四
五
六
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
7
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
给我留言
查看公开留言
查看私人留言
随笔分类
C++(4)
QT(1)
算法(3)
图形学(1)
云平台
随笔档案
2010年10月 (1)
2010年9月 (1)
2010年7月 (3)
2009年12月 (1)
2009年9月 (2)
2009年8月 (1)
搜索
最新评论
1. re: QT显示TGA图片
经测试,在Linux下此方法不行。程序有时候出现异常,有时候会显示错误的图像。我的环境是Ubuntu11.10,Qt4.8.3,Qt Creator2.41。
--彩阳
2. re: 快速判断素数算法
理论依据是什么?
--aa
3. re: 快速判断素数算法
@某W
谢谢,抛砖引玉而已,期待你提出更优秀的方法
--李熙建
4. re: 判断单链表是否有环
@kyle
非常感谢你指出其中的错误
--李熙建
5. re: 快速判断素数算法
这方法很强大~
谢谢~
--某W
阅读排行榜
1. 快速判断素数算法(4176)
2. 判断单链表是否有环(3156)
3. QT显示TGA图片(2009)
4. 时间统计的几种方法(1021)
5. Material Editor(931)
评论排行榜
1. 判断单链表是否有环(4)
2. 快速判断素数算法(3)
3. Material Editor(3)
4. QT显示TGA图片(1)
5. cout问题(0)
判断单链表是否有环
Posted on 2010-09-24 12:30
李熙建
阅读(3156)
评论(4)
编辑
收藏
引用
所属分类:
C++
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)
Feedback
#
re: 判断单链表是否有环
回复
更多评论
2010-09-25 08:16 by
Algorics
如果知道链表的结点数n,那么如果进行n+1次找下一个结点还没到链表的尾部的话就有环。
#
re: 判断单链表是否有环
回复
更多评论
2010-09-26 21:46 by
李熙建
@Algorics
一般情况下,只已知链表的头节点,链表元素个数已知的情况下,你说的方法可以
#
re: 判断单链表是否有环[未登录]
回复
更多评论
2011-05-06 17:49 by
kyle
代码有错...永远返回TRUE.
在对fast初始化的时候应该是fast=head->next;
#
re: 判断单链表是否有环
回复
更多评论
2011-08-01 09:14 by
李熙建
@kyle
非常感谢你指出其中的错误
刷新评论列表
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
相关文章:
cout问题
判断单链表是否有环
temp 对象
CString,string,char*, int之间的转换
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
Powered by:
C++博客
Copyright © 李熙建