劍指offer：鏈表中環(huán)的入口節(jié)點

題目描述
給一個鏈表，若其中包含環(huán)，請找出該鏈表的環(huán)的入口節(jié)點，否則，輸出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

        """
        首先使用快慢指針來判斷是否有環(huán)：初始時快指針和慢指針都指向head，然后快指針每次走2步，
        慢指針每次走1步，如果有環(huán)，那么在快指針走完2步之后一定會相遇。證明如下：
        情況1：相遇前快指針落后慢指針1步，那么再走一次之后快慢指針相遇
        情況2：相遇前快指針落后慢指針2步，那么再走一次之后快指針落后慢指針1步，回到情況1
        情況3：相遇前快指針落后慢指針n步，那么再走一次之后快指針落后慢指針n-1步，經(jīng)過n-1次之后
              回到情況1
        因此，如果鏈表存在環(huán)，那么在快指針走完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

        """
        如果存在環(huán)，那么在第一次快慢指針相遇的時候?qū)⒖熘羔樦赶騢ead，然后快指針和慢指針一起以每次
        走1步的速度移動，當(dāng)?shù)诙蜗嘤龅臅r候就是環(huán)的入口。證明如下：
        假設(shè)第一次相遇的時候慢指針走了N步，那么快指針就走了2N步。如果慢指針繼續(xù)走N步那么就會回到
        第一次相遇的位置，而此時讓快指針從head開始走N步也會到達第一次相遇的位置。

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

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

        return fast