面试题：链表环的检测
去年听师兄讲了一道链表环的问题，给出的解法是：用两个指针p1、p2，它们初试都指向链表头，然后开始向后移动。
指针p1每次移动一步，p2则每次移动两步。如果在移动过程中p2到达链表末端了，表明该链表无环。如果在移动过程中p1和p2相遇了，那么就表示链表有环。
师兄又讲了如何求环的长度，虽然方法同样简单，但是我不是很能理解。就是上面的算法，我也不能确定结果一定正确。师兄说关键在于p2每次都比p1多走一步。
昨天下午又和师弟聊到了这个话题。终于理解了这个算法，同时师弟还之处，从开始到第一次相遇p1所走的步数（x+y，其中x是在直线上走的步数，y为环上所走步数），是环长度n的整数倍。
下面我想说说为什么这个环检测算法有效。且后面的讨论都是针对确实存在环的链表的情况，因为如果一个链表无环的话，那么p2在移动的过程中一定会遇到空指针，即标识链表结束。
假设我们有一个环如图所示：
是链表进入环的位置。
。则经过y步之后，p2将赶上p1，两者相遇。由此，我们已经证明在存在环的链表上，当p1、p2每次移动的步数之差为1时，他们一定相遇。且当他们都在环上同一点出发的情况下，下次相遇之前所走的步数是环的长度。
下面我们证明他们从链表头开始走，一直到的第一次相遇所走的步数（x+y），刚好是圆环的长度n的整数倍。
首先，p1走了x步到达
（可能已经转了几个圈，也可能还没有）；而如果他从
继续往前走y步，就回到了它进入圆环的起点
；可以推知p2与p1从链表起点开始，第一次相遇在 之后的y步。
由上可知，x+y一定是n的整数倍。而x+y恰好是p1在第一次与p2相遇时所走的步数。证明完成。
评论