问题来源:面试提问
判断链表是否有环
经典问题,使用快慢指针解决。
寻找入环点

我们设起点到入环点的长度为a,从入环点到快慢指针相遇的位置的长度为b,环长为c。
那么在快慢指针相遇的时刻,慢指针总共走过了s = a + b
的长度,同时快指针总共走过了2s = a + b + nc ===> 2s = s + nc
的长度。对两个公式进行合并化简的结果为a = c - x
。
由该等式可以知道,从起点开始到入环点的长度和相遇点到入环点的长度相同。即,在相遇时,在链表头再安排一个新的慢指针,并让环中的慢指针继续行走。最终这两个慢指针相遇的点就是链表的入环点。