我没仔细看答案,但是注意到时间(还是空间?)复杂度为2N,所以我有一新想法:

dannyp (Danny)
另COPY一个链表(为了不修改原链表),从FIRST开始,将访问过的节点DATA由小到大付值,然后再从FIRST开始访问,当发现NOW->NEXT->DATA<=THIS->DATA时,即为CLOSE.
原理, 判断是否为闭环,只要判断下NEXT是否穿过以前走过的路.即判断是否穿过以前路的开端和结尾,即 开端<= NEXT->DATA <=结尾。
时间,空间复杂度均为2N
此算法虽然没有MS的好,但是还有改进的余地,
(#144136@0)
2001-7-25 -05:00

回到话题: 看了#142300,也来贴一道MS研究所在中国招聘的考题......

回到论坛: HOME枫下论坛枫下论坛主坛工作学习IT技术讨论

URL:   
http://www.rolia.net/zh/post.php?f=0&p=144136