Microsoft : 找出带环单链表的环起始节点

找出带环单链表的环起始节点
比如 ： 1，2，3，4，5，6，3，4，5，6，3.....
3就是答案

这个题我个人认为没啥意思，太取巧了

回复 2# holyzz


    就好像两个人在跑道上赛跑，跑得快的跑着跑着总会比跑得慢的快一圈。。。

一般比较经典的 方法应该就是用 一个 快指针比如步进2，一个慢指针比如步进1，如果快指针能找到NULL的点说明无环；如果有一天快指针和慢指针的的指向的点相等，说明这个就是环的起点。
其他方法哈希表什么的也很常见
holyzz 发表于 2011-5-18 06:43

    不对啊，审题. 你那只能找在环中的一个节点，不能确定是第一个起始节点，看题目给的例子

回复 2# holyzz
只能确定是否有环，没办法确定起点

回复 4# wwwyhx
那个离答案也差的不多了。第一次相遇的时候两个指针差的是loop长度的整数倍，然假设为l，然后还是取两个指针，第一个先走l步然后两个一起每次走一步，再次相遇的地方就是起点了。

回复  wwwyhx
那个离答案也差的不多了。第一次相遇的时候两个指针差的是loop长度的整数倍，然假设为l，然后还是取两个指针，第一个先走l步然后两个一起每次走一步，再次相遇的地方就是起点了。
darksteel 发表于 2011-5-18 13:28

    不是吧，你怎么证明呢

回复 8# holyzz
没有，你说的方法是可以的，只要像我6楼说的那样，再走一遍就能找到起点。第二遍走的时候很容易证明在loop起点两指针一定相遇，因为先走的那个比后走的领先l步，可以认为是领先k(k>=1)圈，当后走的指针到达起点的时候，先走的肯定也在起点的位置。

回复  holyzz
没有，你说的方法是可以的，只要像我6楼说的那样，再走一遍就能找到起点。第二遍走的时候很容易证明在loop起点两指针一定相遇，因为先走的那个比后走的领先l步，可以认为是领先k(k>=1)圈，当后走的指针到达起点的时候，先走的肯定也在起点的位置。
darksteel 发表于 2011-5-19 02:51

    不对，你这个找到的是第一次相交的环内节点，但是这个节点不一定就是环的起始节点(注意这个其实节点的意思)。一个很意外的方法是：当第一次找到环内的一个节点后，把这个环break掉，这样问题就变成了相交链表求交点问题了，最后需要还原。

怎么样，很无聊的算法题吧，亏微软想的出来