经典面试题 如何判断链表有环
参考链接
http://blog.csdn.net/thefutureisour/article/details/8174313
http://blog.csdn.net/liuxialong/article/details/6555850
题目背景
给定一个单链表，只给出头指针(h)，允许的时间复杂度(O(n))，空间复杂度(O(1))
如何判断链表有环
- fast指针：步长为(2)，起点为头节点
- low指针：步长为(1)，起点为头节点
- 如果链表有环，那么fast指针和low指针肯定相遇
如何得知环的长度 (r)
- 很容易知道两个指针肯定在环内相遇，假设两次相遇时间间隔t
- 这就是小学学过的追及问题。速度差(v=1)，时间(t)，(需要追及的距离=环长=v*t=t)
如何找到环的入口点
- 假设头节点到入口点距离(a)，入口点到第一次相遇点距离(x)，第一次相遇时间(t)，链表总长(L)
- 结论一：第一次相遇时low指针肯定还没在环内走完一圈，那么(t=a+x（1）)
- 证明：low指针位于入口点的时候，fast指针和它可能的距离取值范围在([0,r-1])。下次相遇意味着fast指针追上low指针，fast最迟经过(r-1)时间追上low指针，这时候low指针还没走完一圈。得证。
- 容易知道，第一次相遇时，fast指针已经在环内走了(n(n>=1))圈，那么(2*t-t=nr（2）)
- 结论二：第一次相遇点到入口点的距离=头节点到入口点的距离。因此，在头节点、第一次相遇点各设一个指针，每次各走一步，两个指针必定相遇，且第一次相遇点为环入口点。
- 证明：由(1)式(2)式得(a+x=nr)，化简得(a+x=(n-1)r+r)，(a=(n-1)r+r-x)。这说明：从头结点到入口点的距离，等于从第一次相遇点转了((n-1))圈，再走到入口的距离。得证。
如何求得链表长度 (L)
- (L=a+r)