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

回复 10# wwwyhx
上学期我们算法做过这个题，这个解答应该没问题的。上面已经说过在loop的起点处肯定会相遇，因为先走的比后走的领先k圈，所以后走的到环的起点时，先走的也一定在环的起点，这肯定是没错的

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

怎么样，很无聊的算法题吧，亏微软想的出来
wwwyhx 发表于 2011-5-19 11:56

是挺取巧的，指针真是个神奇的东西。

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

对，没错，是个好办法。这题还真难

@wwwyhx 4楼

两个链表不可能两个交点的吧...
因为链表的每个节点只有一个后继节点。。。

careercup 上的题吧
https://github.com/yuren12345/careercup/blob/master/circle.cpp

wwwyhx 发表于 2011-5-19 11:56
不对，你这个找到的是第一次相交的环内节点，但是这个节点不一定就是环的起始节点(注意这个其实节 ...

嗯，惊奇的思路

第一次相遇的时候，第一个走了l1 = a + i*n + b, 第二个走了l2 = a + j * n + b。a 是从头到环起点的位置，b是从环起点的位置到相遇的位置的距离。n是环的长度，相遇时，第二个走的距离是第一个的2倍， l1 = l2 - l1 = (j - i) * n也就是，慢的走的总的距离是环的整数倍。这个时候，将快的指针指向链表的头，两个指针同时走，每次一个。第二次相遇，快的走了a步，慢的也走了a步，此时，慢的一共走了(j - i) * n  + a 步。说明是在环的起点。