题解 | #链表中环的入口结点#

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        #双指针法
        slow=pHead#每次走一步
        fast=pHead#每次走两步
        while(fast and fast.next):
            slow=slow.next
            fast=fast.next.next
            if(slow==fast):#确认有循环
                break
        if(not fast or not fast.next):#可能是{1,2},{}无循环推出
            return None
        #设起点到入口为X，slow走了S，则入口到目前slow所在点的半圆长为S-X,
        #经计算，另一半圆=2*S-X-(S-X)*2=X
        #则，将fast置于起点，slow继续走完另一半圆，他们会在入口相遇
        fast=pHead
        while(fast!=slow):
            slow=slow.next
            fast=fast.next
        return fast
        # write code here