×

Loading...

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 -04:00
This post has been archived. It cannot be replied.
Page address has been copied. To share, click to copy page address.
Share Online by QR Code

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

Back To Forum: HOME枫下论坛枫下论坛主坛工作学习IT技术讨论