链表交点问题也属公司青睐的专题之一，一般依靠双指针来解决，主要分为链表判环和链表相交两大专题。
142. Linked List Cycle II
题意：
判断链表是否有环，若有环，则返回环入口节点。
思路：
这题就是典型的快慢指针问题，代码很简单，但具体理论证明却十分值得研究。
首先先说解法， 分两部分，判环和寻找入口：
判环部分，设置两个指针（快指针fa一次走两个节点，慢指针sl一次走一个节点），若快指针走到了链表尾即空节点则说明链表无环，否则在环中快慢指针必能相遇。
寻找入口部分，慢指针不变，快指针移至链表头，并也开始一步一节点的行走，双指针同时移动，相遇处即为环入口
理论证明：
判环部分不难理解，如操场跑圈一般，快者定能追上慢着。然而寻找入口部分就显得十分玄学了，下面我们开始理论证明。
假设链表由长度为
的单链和长度为
的环两部分构成，判环阶段当快慢指针相遇时，慢指针走了
步。<
版权声明：本文为Owen_Q原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。