链表的环的入口 LeetCode142 Linked List Cycle II

LeetCode原题：

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

即找到链表的环的入口点。它的前一题是检测环是否存在。检测环存在可以有3种方法：
1.暴力法；一直遍历下去，设置1秒或更长的超时时间，到了返回存在环；
2.使用map保存遍历过的node，如果下一个node在map中存在，那么存在环；
3.快慢指针法；快指针每步走两格，慢指针每步走一格，如果两指针能相遇，那么说明存在环；
存在环的代码如下：

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if fast == slow:
            return True
    return False

但是怎么找到环的入口点呢，这里仍然用到了快慢指针，如下图：

假设快指针fast和满指针slow最终在a点相遇，那么快指针共走了慢指针两倍的距离
$l_{fast}=2l_{slow}$lfast​=2lslow​
假设环的周长是C，那么快指针走过的距离减去慢指针走过的距离是周长的整数倍，即：
$l_{fast}-l_{slow}=l_{slow}=nC$lfast​−lslow​=lslow​=nC
在a点相遇后，我们让慢指针从头开始走，快指针从a点开始走，且每次走一个节点，那么他们必然还会在a点相遇，因为他们都走了$l_{slow}$lslow​的距离，满指针会走到a，而快指针走了n圈后，又回到a。又因为他们都是一步一步走的，那么从进入环的那一刻他们就已经重合了，从而得到快慢指针的第一个重合点就是环的入口，代码如下：

def detectCycle(head):
    slow = fast = tmp = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow == fast:
            while 1:
                if tmp == fast:
                    return tmp
                else:
                    tmp, fast = tmp.next, fast.next
    return None