| « | August 2025 | » | | 日 | 一 | 二 | 三 | 四 | 五 | 六 | | | | | | 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 | | | | | | | |
|
公告 |
|
俺就是Hal9000，心情不错中... |
| Blog信息 |
|
blog名称:dhunter's blablab
日志总数:16
评论数量:17
留言数量:2
访问次数:140052
建立时间:2004年11月2日 |
| |
|
 [sense]啧, 差距啊
软件技术
dhunter 发表于 2004/11/22 20:18:11 |
|
今天到网上查一个问题，C 专家编程里的，让我看到了差距，前人大牛啊
算法求解!如何判断一个单向链表是否有环路?
flw 回复于：2004-09-20 13:18:10
用两个指针，一个的步长为 1，另外一个的为 2，从表头开始一起往前走，如果相遇，表明有环路，否则就是没有了。
win_hate 回复于：2004-09-20 18:50:29
这个问题应该有很长历史了，《C 专家编程》的附录，程序员工作面试的秘密就提到过这个问题。在这 里我试图对这个问题做一个数学的分析。 如果单链表里存在重复的点，则该链表中包含一个环，事实上，可以用下面的图来表示 这使我想起 Pollard 的 "rho" 算法，事实上本问题与 "rho" 算法有一个共同点，寻找一个碰撞。 从这个图我们可以看到，如果一个单链表里出现了重复的点，则从表头开始走，无论以什么步调，必定 会落到环中。所以我们可以肯定，如果以某个步调走，碰到了NULL，则该链表无重合点。 尝试用两个指针，以不同的步调前进，如果他们能相遇，必定是在环中。假定指针 p 以步调 f 前进，q 以步调 g 前进，g>f。则 q 先进入链表的环。有一种情况很特殊，就是：在 p 刚进入环的时候就与 q 相遇。这是一个小概率事件，我们排除它，不考虑这种情况。可以认为： p 进入环的时候，偏移为 a, 而同时 q 的偏移为 b， 环的长度为 n。（参考下面的图） 往后， p, q 就在圈内打转，它们在x 步后重合的条件为： fx + a = gx + b (mod n) (f-g)x = b-a (mod n) 上式有解等价于 (f-g, n) | (b-a)。 但是，我们在事前不知道 n, 不知道 b-a， 所以唯一能确保 (f-g, n) | (b-a) 成立的是 f-g =1。 只要 f-g = 1, 我们就能一定能检测出重合的情况，这是一个充分条件。 而一旦 p 刚进入环时与 q 不等，(f-g, n) | (b-a) 就成为检测重合的必要条件。前面一些朋友说 f,g 互素或 f, g 不同即可的观点是错误的。从 (f-g, n) | (b-a) 这个条件应该能找到反例。但这个我就 留给有兴趣的朋友了。 f = 1, g = 2 未必是最好的，因为如果 "rho" 的尾巴很长，p 要花费很多工夫才能进入环。此外，虽 然步调大的时候，可能要跑好几个圈才能覆盖整个环，甚至在很多情况下不能覆盖整个环，但它跑一圈 的时间也相应减少，足以抵消。可惜的是，分析最优的选择，超出了我的能力范围。
500)this.width=500'>
500)this.width=500'>
yangtou 回复于：2004-09-20 19:28:07
不需要考虑细节情况，就可以判断可能性 x=pn/(a-b) > m/b 只要改变p的值就可以找到合适的x，x>m/b所以只要ab不等就必定相遇 另外如果m较小比如0,由x=pn/(a-b)(不考虑m/b) 则x只决定于a-b(只要改变p就可以得到x的合适的最小值，而p是决定于a-b的) T=(au+bu+av+w)x，在(a-b)一定的情况下，ab取值越小T越小 |
|
|