看了水中的鱼的解题报告，用快慢两个指针, 很巧妙的解法。快指针fast一次走两步, 慢指针slow一次走一步, 假设环外有X个节点, 即从head走X步可以到达环的第一个节点。再假设环有Y个节点, fast和slow指针在环中的第K+1个节点相遇。那么相遇时fast指针和slow指针都走了 X + mY + K 次。因为fast一次走两步, 所以实际走过的节点数fast是slow的两倍, 两者的差一定是Y的倍数, 2(X + mY + K) - (X + mY + K) = nY, 于是就有 X + K = (n - m)Y。

    此时让fast ＝ head, 从头开始走, slow在原位置继续走, 两者都一次走一步, fast和slow再次指向同一节点时, 这个节点就正好是环的第一个节点, 而且此时fast和slow正好走了X步。因为fast从head走了X步正好进入环, slow从原来位置走X步, 根据上一段末的等式, 有 X + mY + K + X = X + mY + (n - m)Y = X + nY, 即slow此时也在环的第一个节点。

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param head, a ListNode
    # @return a list node
    def detectCycle(self, head):
        if head == None: return None
        fast = slow = head
        hasCycle = False
        while fast != None and fast.next != None:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                hasCycle = True
                break
        if not hasCycle: return None
        fast = head
        while fast != slow:
            fast = fast.next
            slow = slow.next
        return fast