Topic: 看了#142300，也来贴一道MS研究所在中国招聘的考题...... @枫下论坛 The Rolia Forum

工作学习 / IT技术讨论 / 看了#142300，也来贴一道MS研究所在中国招聘的考题...... -xxjjs(东方射日); 2001-7-24 {231} (#142594@0)
有一个有限长度的单向链表：
ln {
ln * next;
DATA
}
首指针为FIRST；其中可能存在一个闭合的环，要求写一段C程序，确定是否存在闭合的环。
要求无论该链表长度为多少（有限长），能确保该段代码在有限时间和有限内存空间限制内正确得出结果！

再做一个链，把前一链的节点逐个放入逐个比较。 -guest:; 2001-7-24 (#142599@0)

其实这个问题很简单。 -guest:; 2001-7-24 (#142618@0)
错！请注意“能确保该段代码在有限时间和有限内存空间限制内正确得出结果”，你再申请一个链，能确保内存空间够吗？虽然是有限长，但是可能为100个节点，也可能有50亿个节点。 -xxjjs(东方射日); 2001-7-24 (#143606@0)

you can create a stack. In the stack, you search the every next point and push current point of the node. -jami(jami); 2001-7-24 {155} (#143058@0)
If you find the point in the stack, that is link loop in your link table. For more efficient search, you can sort the points in the stack before searching.

WRONG! How much the stack you apply?Do you know how long the link? Can you sure the memory is enough for you? -xxjjs(东方射日); 2001-7-24 (#143620@0)

MS研究所的招聘题不会那么简单的！给大家一个提示：你永远不知道链表有多长！你不知道闭合环从第几个节点开始！所以你只能申请确定个数的节点。 -xxjjs(东方射日); 2001-7-24 (#143609@0)

Can you post your answer? Maybe we will meet it in another interview!!!Thanks!!!!!!!! -guest:; 2001-7-24 (#143633@0)

Easy, ... -guest:Sean; 2001-7-24 {194} (#143657@0)
Because of the limited space, we can set a possible max length of the list. Then, we go through the list, count the number of the node. If the number is larger than the possible max length, ...

WRONG! You never know how long the ling will be. How can you set a "possiblely" number? It is limited in mathematic, but may be larger than the largest number in computer. How can you "SURE"? -xxjjs(东方射日); 2001-7-24 (#143673@0)

A possible max length is not the actual the length of node. -guest:Sean; 2001-7-24 {473} (#143689@0)
It's a possible max length. F.g. A node need 12 bytes. In a XXMbytes memory computer, we can set the possible max length to use up all the memory of the computer. That's XXM/12bytes.

We go throught the list, and count the number of the node, if the number is larger then the value XXMbytes/12bytes, we can say there is a cirle in the list.

Because we don't need other more memory, and just go throught the list, and count the number. we don't need tough cpu time.

Perhaps this is a doable way. But be a compatible program, you should chek the owner computer's memory, check the node occupancy and calculate the possible MAX number. -xxjjs(东方射日); 2001-7-24 (#143713@0)

MS的答案，大家看是不是很巧妙！（我是没有想出来，不过看了答案后，再仔细想想，好像在题目“确保”的限制下，这几乎是唯一的方法） -xxjjs(东方射日); 2001-7-24 {433} (#143685@0)
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

大家还有没有其他答案？－－仔细想想“确保”的条件。

妙！我有一个笨办法，时间用的比较多。请指教！ -birdincage(birdincage); 2001-7-24 {212} (#143796@0)
ln *a;
ln *b;
long i,j;//或 double i,j；

for (a=FIRST, i=0; a; a=a->next,i++)
{ for (b=FIRST, j=0; b!=a; b=b->next, j++);
if (j<i) return CLOSE;
}
return OPEN;

问题是节点个数要能够用double表示。

当然在点个数要能够用double表示的前提下是OK的，空间复杂度为两地址，可是时间复杂度太高了，为<=n*n（最坏情况为1->2->3->4......->n->n） -xxjjs(东方射日); 2001-7-25 (#143831@0)

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

空间复杂度应该是N！吧？可能我说的不对 @@ -antmm(antmm); 2001-7-25 (#144151@0)
你的方法有以下问题： -xxjjs(东方射日); 2001-7-25 {382} (#144430@0)
1, MS答案中空间复杂度为2,而你的复杂度为N，依据题意，链表长度有限仅仅是数学上的有限，而计算机内存则是现实的有限，我们就是要用实际的限制来完成数学上的有限。所以空间复杂度不能和N相关。
2,另外copy一个链表不知你如何copy？只拷贝DATA毫无意义，copy指针next如何实现？定义了一个newln进行copy那么，newlan->next指向谁？
3,也许我没有理会你的思路，不过你能否用计算机语言描述一下，看看如何实现？

改正。空间复杂度是N。另回答问题 -dannyp(Danny); 2001-7-25 {597} (#144572@0)
我想我的解法有问题。但是我看了一下别人的解发，发现还没有我的好。
我的解法的问题在于在不改变链表的情况下，空间复杂度为K*N（K为常数），但是若允许改变链表，则空间复杂度为1（直接修改原链表的DATA）。
不过直接修改原链表，虽然原题没有限制，但近似无赖的行为了。
真的远不如MS的办法巧妙。
不过不知道有没有人能顺着我的思路再走一步，将空间复杂度减少到与N无关？
（关于空间复杂度不能与N发生关系，我认为原题并没有限制，因为MS的解法时间复杂度也为2*N，若N为无穷，时间也为无穷。）
射日兄，对，新链表NEXT=旧链表的NEXT，而旧链表的NEXT指向新链表的THIS，当算法完毕时再将旧链表的指针根据新链表的指针值修改回去即可

N是有限的的，不是无穷，这在题目中写得很清楚。只要他是有限的，我们在时间上总可以确保完成。但是我们不能确保能申请到足够的内存。我想这也许就是空间复杂度不能为N但是时间复杂度允许为N的原因吧。 -xxjjs(东方射日); 2001-7-25 (#144664@0)

另COPY链表的算法 -dannyp(Danny); 2001-7-25 {115} (#144578@0)
In Old, NEW;
...
COPY(...)
{
aNEW=new In;
aNew->next = currOldNode->next;
currOldNode->next = &aNew

}

谢谢！明白了，你新建的链表直接间隔地插在原链表中间。不错，好思路。那其实在插链表的时候就可以进行CLOSE/OPEN的判断了。 -xxjjs(东方射日); 2001-7-25 (#144676@0)

不好，不好！说了要考虑空间的问题，就不能增加一个新的链表。能这样的话，最简单的方法是在ln 中加一个域bool, 初始为0，访问过就变1，最简单。 -birdincage(birdincage); 2001-7-25 (#144935@0)

也许我真的很笨，但是我还是弄不明白a为什么不能保持不动，速度不是更快吗？ -babyface(Tracy); 2001-7-25 (#144192@0)

你并不知道闭合的环从第几个节点开始，a如果不动，它可能不在闭合环中，b永远到不了a。例如：1->2->3->4->5->3...的链表中，a为1，b却永远在3->4->5->3->4->5....中转圈。 -xxjjs(东方射日); 2001-7-25 (#144410@0)

从FIRST开始，记录该节点为P，比较节点P和后一节点，若节点P地址比后一节点地址大，则交换两节点位置，并记录地址大的节点于节点P，如此下去，如果有发现节点P和下一节点地址相同，则有闭合环 -beware(断线风筝); 2001-7-24 (#143741@0)

没看明白，能详细说说吗？或给个示例。谢谢！ -xxjjs(东方射日); 2001-7-24 (#143757@0)

在一个闭合环里，地址最大的节点是唯一的。 -beware(断线风筝); 2001-7-24 (#143782@0)

节点P用于记录以搜索的节点里地址最大的；把地址大的节点往后移是为了保证地址最大的节点可以移到闭合环里 -beware(断线风筝); 2001-7-24 (#143801@0)

首先，地址最大的节点可能不在环中，其次，你将其移到环中能实现判断是否存在闭合环的要求，但是这样就更改了链表的结构。可以讲，你实现了题目的要求，但是在实际应用中，做为一个判断是否存在闭合环的函数，是不适用的！谢谢你的思路！ -xxjjs(东方射日); 2001-7-25 (#143825@0)

只是为了挑战你说唯一的方法 -beware(断线风筝); 2001-7-25 (#143847@0)

见笑见笑，在下愚钝，没有想出其他方法，所以“唯一”只相对本人，各位高手指教，在下受益匪浅。 -xxjjs(东方射日); 2001-7-25 (#143927@0)

还有一方法可以避免改变链表结构。定义一该机器所能允许的最小地址的节点插在FIRST，按照同样的方法（只是节点P记录地址最小的和把地址最小的节点往后移），就可以判断是不是闭合环。判断完毕把此最小地址的节点从链表中删除。 -beware(断线风筝); 2001-7-25 (#143866@0)

这好像不对：假设最小地址为minadd＝1，进行运算minadd->next时几乎肯定会coredump。因为最小地址空间几乎肯定被占用，而你新申请的空间地址并不能确保为最小或最大，再想想还有没有其他办法？ -xxjjs(东方射日); 2001-7-25 (#143948@0)

try my way: just go through the link and count the node number P, if P is bigger than the real node number N and still not stop , that's must be a close cirlce. -guest:coder; 2001-7-25 (#144423@0)

Where can you get the 'N'?? -xxjjs(东方射日); 2001-7-25 (#144441@0)