MS的答案,大家看是不是很巧妙!(我是没有想出来,不过看了答案后,再仔细想想,好像在题目“确保”的限制下,这几乎是唯一的方法)

xxjjs (东方射日)
ln *a;
ln *b;

a=FIRST;
b=FIRST;
for (;;)
{
b=b->next;
if (b == a) return CLOSE;
if (NULL == b) return OPEN;
b=b->next;
if (b == a) return CLOSE;
if (NULL == b) return OPEN;
a=a->next;
}

看明白以上代码了吗?是不是很简单但是非常巧妙?
空间复杂度:2个节点地址; 时间复杂度:《=2N (假设链表长度为N)
原理:在闭合的跑道上,B以两倍于A的速度前进,必定会追上A

大家还有没有其他答案?--仔细想想“确保”的条件。
(#143685@0)
2001-7-24 -05:00

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

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

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