是技術,更是藝術
一心編程,就沒有解決不了的問題
posts - 9, comments - 11, trackbacks - 0, articles - 0
導航
C++博客
首頁
新隨筆
聯系
聚合
管理
<
2011年8月
>
日
一
二
三
四
五
六
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
8
9
10
常用鏈接
我的隨筆
我的評論
我參與的隨筆
留言簿
給我留言
查看公開留言
查看私人留言
隨筆分類
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.?快速判斷素數算法(4239)
2.?判斷單鏈表是否有環(3170)
3.?QT顯示TGA圖片(2079)
4.?時間統計的幾種方法(1039)
5.?Material Editor(959)
評論排行榜
1.?判斷單鏈表是否有環(4)
2.?快速判斷素數算法(3)
3.?Material Editor(3)
4.?QT顯示TGA圖片(1)
5.?temp 對象(0)
判斷單鏈表是否有環
Posted on 2010-09-24 12:30
李熙建
閱讀(3170)
評論(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
博問
Chat2DB
管理
Powered by:
C++博客
Copyright © 李熙建
中文字幕精品久久
|
亚洲欧美一级久久精品
|
久久国产亚洲精品无码
|
国产欧美一区二区久久
|
99久久无码一区人妻a黑
|
99久久99久久
|
久久久免费观成人影院
|
色婷婷综合久久久久中文字幕
|
伊人久久大香线蕉综合5g
|
亚洲综合久久久
|
国产69精品久久久久777
|
亚洲精品国精品久久99热
|
午夜欧美精品久久久久久久
|
久久精品一区二区三区不卡
|
久久中文精品无码中文字幕
|
精品蜜臀久久久久99网站
|
国产99久久久国产精免费
|
99久久国产综合精品女同图片
|
性做久久久久久久久
|
国产成人久久精品一区二区三区
|
久久精品国产只有精品66
|
久久久久久亚洲Av无码精品专口
|
国产精品久久精品
|
99久久香蕉国产线看观香
|
成人午夜精品久久久久久久小说
|
99久久无色码中文字幕人妻
|
国产精品成人精品久久久
|
国产午夜福利精品久久2021
|
久久久久av无码免费网
|
国产精品女同一区二区久久
|
久久国产精品久久精品国产
|
狠狠精品久久久无码中文字幕
|
无码国产69精品久久久久网站
|
久久精品无码一区二区三区日韩
|
国产亚洲美女精品久久久久狼
|
亚洲AV日韩精品久久久久久
|
久久99热这里只有精品66
|
无码人妻久久一区二区三区蜜桃
|
99久久精品国产毛片
|
91精品国产高清久久久久久91
|
久久精品成人国产午夜
|