某互联网公司面试题(二)

接上贴http://lgsun592.iteye.com/admin/blogs/1066179，这也是其中的一道面试题

问题：一个链表可能包含环，如何检测并确定环的位置，如图：



?


方法有2：

1.记录法，通过某种方式把访问过的记录记录下来，然后访问下一个节点的时候查询下访问记录（我当时只想到了此方法，唉）；

如果是外部标记的话，需要遍历1+2+...+(P+L-1)+P+(P+L)个节点，约O((max(P,L))^2)，程序实现的就是此种方法

如果是内部标记的话，只需要遍历P+L个节点，速度最快的了

2.追赶法，类似在操场跑圈，两人同时起步，快的人和慢的人第一次相遇的时候，快的肯定比慢的多跑一圈，以此进行推算

第一次跑：两人同时从起点出发，第一个人P1速度为1，第二个人P2速度为2，相遇的时候P1跑的路程N=P+C，P2的路程=2N，可以推出此园的周长KL=P+C=N(K=1,2...)

第二次跑：P1的接上次位置，速度为1，P2从起点出发，速度为1，这次经过距离P后2人相遇，即在圆的起点相遇

，希望大家早日找到自己喜欢的工作哦。

?????? 我是在洗澡的时候完成的此题的编码构思，所以一不小心和地板来了个亲密接触


参考资料：http://blogold.chinaunix.net/u1/41845/showart_2019391.html
?
   有些东西做不出来就进不去，那就搞不定了。。。。。  有些东西做不出来就进不去，那就搞不定了。。。。。
想进入好的公司真的需要做足功课。不过对于这些算法题，我不行，也不打算浪费青春去学。

似乎和找出一个List里两个值相同的元素的索引是一个解法，只不过这里是比较两个节点的相等（内存地址相同），再思考。    17 楼    sebatinsky    2011-06-08              菜鸟从中飞过，，，。心慌慌。