标题:一个面试题
取消只看楼主
missiyou
Rank: 5Rank: 5
等 级:贵宾
威 望:16
帖 子:531
专家分:218
注 册:2007-10-9
结帖率:100%
 问题点数:0 回复次数:3 
一个面试题
问,“如何检测链表是循环链表”
如果长度为N的链表如何检测
如果允许做标记,如何检测,
最难的 如果链表的循环在任意位置,任意长度,如何检测是循环链表。
恩,就是这道题,
搜索更多相关主题的帖子: 面试 
2007-12-09 22:58
missiyou
Rank: 5Rank: 5
等 级:贵宾
威 望:16
帖 子:531
专家分:218
注 册:2007-10-9
得分:0 
本人只会说一个我自己的一个方法,别的解法都是书上的,我在这里不说了
就是如何检测N长度的表。
我自己的想法就是,一个表,长度为N,如果这个表没有循环的话,那么,长度刚好N。如果大于N那么说明有循环。这样就好做了,
设一个头指针,遍历,在定义一个计数器,如果这个计数大于N。那么,循环。
2007-12-10 20:36
missiyou
Rank: 5Rank: 5
等 级:贵宾
威 望:16
帖 子:531
专家分:218
注 册:2007-10-9
得分:0 
,设二个指指针,p1,p2.排除最坏的情况。p1指向第一个元素,p2指向第三元素。特殊的就是如果第二个元素就是循环的话,那么就不能找到了,这样,p1=p1->next; p2=p2->next->next; 如果循环,最终,p1=p2; 就像,在操场上跑步,快的会追到慢的,如果追到话,证明循环,不管这个表有多长,还是在那个地方;
2007-12-10 21:33
missiyou
Rank: 5Rank: 5
等 级:贵宾
威 望:16
帖 子:531
专家分:218
注 册:2007-10-9
得分:0 
12345
3524
1234
2007-12-10 21:39



参与讨论请移步原网站贴子: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