搜索
编程论坛
→
开发语言
→
『 数据结构与算法 』
→ 一个面试题
标题:
一个面试题
取消只看楼主
missiyou
等 级:
贵宾
威 望:
16
帖 子:531
专家分:218
注 册:2007-10-9
结帖率:
100%
楼主
问题点数:0 回复次数:3
一个面试题
问,“如何检测链表是循环链表”
如果长度为N的链表如何检测
如果允许做标记,如何检测,
最难的 如果链表的循环在任意位置,任意长度,如何检测是循环链表。
恩,就是这道题,
搜索更多相关主题的帖子:
面试
2007-12-09 22:58
missiyou
等 级:
贵宾
威 望:
16
帖 子:531
专家分:218
注 册:2007-10-9
第
2
楼
得分:0
本人只会说一个我自己的一个方法,别的解法都是书上的,我在这里不说了
就是如何检测N长度的表。
我自己的想法就是,一个表,长度为N,如果这个表没有循环的话,那么,长度刚好N。如果大于N那么说明有循环。这样就好做了,
设一个头指针,遍历,在定义一个计数器,如果这个计数大于N。那么,循环。
2007-12-10 20:36
missiyou
等 级:
贵宾
威 望:
16
帖 子:531
专家分:218
注 册:2007-10-9
第
3
楼
得分:0
,设二个指指针,p1,p2.排除最坏的情况。p1指向第一个元素,p2指向第三元素。特殊的就是如果第二个元素就是循环的话,那么就不能找到了,这样,p1=p1->next; p2=p2->next->next; 如果循环,最终,p1=p2; 就像,在操场上跑步,快的会追到慢的,如果追到话,证明循环,不管这个表有多长,还是在那个地方;
2007-12-10 21:33
missiyou
等 级:
贵宾
威 望:
16
帖 子:531
专家分:218
注 册:2007-10-9
第
4
楼
得分:0
12345
3524
1234
2007-12-10 21:39
4
1/1页
1
参与讨论请移步原网站贴子:
https://bbs.bccn.net/thread-191428-1-1.html
关于我们
|
广告合作
|
编程中国
|
清除Cookies
|
TOP
|
手机版
编程中国
版权所有,并保留所有权利。
Powered by
Discuz
, Processed in 0.145592 second(s), 8 queries.
Copyright©2004-2025, BCCN.NET, All Rights Reserved