【解题报告】【lintcode103】Linked List Cycle II

题意

给出一个链表,可能会有环(从某一点开始,经过一段之后又回到这个点),找出这个环的开始点
使用O(n)的复杂度解决

解答

我们可以设置两个指针,一个每次前进一步,一个每次前进两步
那么,如果有环,这两个指针必定在环里某一个点相遇,这时候
假设环外到环开始点的路程为a
假设慢指针在环内走了b
环剩下的部分距离为c
那么,我们可以得到
(a+(b+c)+b)/2 = a + b
左边是快指针走过的距离除以速度,右边是慢指针距离除以速度
化简之后可以得到
a = c
所以,从相遇点开始,把慢指针放到链表开头,然后和快指针一起以1的速度移动,再次相遇的地方就是环的开始点了
如下图
QQ截图20160520140221

代码

u3coding

A software developer

Leave a Comment

Your email address will not be published. Required fields are marked *

*