【leetcode】142. Linked List Cycle II 解题报告

思路：
有环没环快慢指针法就可以判断。这里我们假设有环，如图所示，设环的入口点为B,快慢指针交点为C，为了区分B->C弧和C->B弧，我们分别BxC和ByC来表示。
快慢指针相交时，快指针比满指针多走了一圈，因为快指针每次走两步而满指针每次只走一步，所以相交的时候快指针走了2X步，而满指针走了X步，他们的差就是一圈的长度也就是X。所以：
AB + BxC = X
BxC + CyB = X
得： CyB = AB
所以让一个指针从A出发另一个指针从C出发，只要他们的速度一样，就会相交于入口B。

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        try:
            slow = head
            fast = head
            while(True):
                slow = slow.next
                fast = fast.next.next
                if slow == fast:
                    break
            pNode = head
            while(pNode != slow):
                pNode = pNode.next
                slow = slow.next
            return slow
        except:
            return None