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

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def MeetNode(self, pHead):
        if pHead==None:
            return None
        
        pSlow=pHead.next
        if pSlow==None:
            return None
        pFast=pSlow.next
        
        while pSlow.next!=None and pFast.next!=None:
            if pSlow==pFast:
                return pFast
            pSlow=pSlow.next
            pFast=pFast.next
            if pFast.next!=None:
                pFast=pFast.next
            elif pFast.next== None:
                return None
        
        return None
        
    
    def EntryNodeOfLoop(self, pHead):
        
        #1) 判断是否有环：若无环，返回None
        MeetingNode=self.MeetNode(pHead)
        if MeetingNode==None:
            return None
                                
        #2）若有环，得到环内节点个数
        tNode=MeetingNode
        num=1
        while tNode.next!=MeetingNode:
            tNode=tNode.next
            num+=1
        
        #3）仿照“链表中倒数K个节点”，用双指针得到入口节点。
        Node1=pHead
        Node2=pHead
        for i in range(num):
            Node1=Node1.next
        
        while Node1!=Node2:
            Node1=Node1.next
            Node2=Node2.next
        
        
        return Node1