劍指offer：鏈表中環的入口節點

題目描述
給一個鏈表，若其中包含環，請找出該鏈表的環的入口節點，否則，輸出null。

# -*- coding: utf-8 -*-
# @Time         : 2019-04-23 22:40
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : entryNodeOfLoop.py
# @Blog         : https://blog.51cto.com/jayce1111
# @Github       : https://github.com/SysuJayce

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

class Solution:
    def EntryNodeOfLoop(self, pHead):
        if not pHead:
            return None

        """
        首先使用快慢指針來判斷是否有環：初始時快指針和慢指針都指向head，然后快指針每次走2步，
        慢指針每次走1步，如果有環，那么在快指針走完2步之后一定會相遇。證明如下：
        情況1：相遇前快指針落后慢指針1步，那么再走一次之后快慢指針相遇
        情況2：相遇前快指針落后慢指針2步，那么再走一次之后快指針落后慢指針1步，回到情況1
        情況3：相遇前快指針落后慢指針n步，那么再走一次之后快指針落后慢指針n-1步，經過n-1次之后
              回到情況1
        因此，如果鏈表存在環，那么在快指針走完2步、慢指針走完1步之后一定會相遇，不存在快指針走1步
        之后相遇的可能
        """
        fast = slow = pHead
        hasLoop = False
        while fast.next:
            fast = fast.next
            slow = slow.next
            if fast.next:
                fast = fast.next
            if fast == slow:
                hasLoop = True
                break

        if not hasLoop:
            return None

        """
        如果存在環，那么在第一次快慢指針相遇的時候將快指針指向head，然后快指針和慢指針一起以每次
        走1步的速度移動，當第二次相遇的時候就是環的入口。證明如下：
        假設第一次相遇的時候慢指針走了N步，那么快指針就走了2N步。如果慢指針繼續走N步那么就會回到
        第一次相遇的位置，而此時讓快指針從head開始走N步也會到達第一次相遇的位置。

        既然會同時到達第一次相遇的位置，那么快指針和慢指針在回到第一次相遇的位置之前會有一段共同
        的路，由于慢指針現在只走在環里，說明共同的路出現在環里，而快慢指針的第二次運動的起點不一樣
        因此在快指針到達環的入口的時候慢指針一定也在環的入口，之后兩指針保持相同速度繼續想第一次
        相遇的位置移動。

        所以，如果存在環，那么將快指針(或者另外設一個指針)指向head，然后和慢指針一起一次走1步。
        他們再次相遇的位置就是環的入口(因此此后需要同步移動到第一次相遇的位置)。
        """
        fast = pHead
        while fast != slow:
            slow = slow.next
            fast = fast.next

        return fast