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

import re
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
# class Solution:
#     def EntryNodeOfLoop(self, pHead):
#         # write code here
#         if pHead is None:
#             return None
#         hash_table = set()
#         while pHead:
#             if pHead not in hash_table:
#                 hash_table.add(pHead)
#             else:
#                 return pHead
#             pHead = pHead.next
#         return None
# x+y=(n−2m)(y+z)
# x = (n-2m-1)(y+z) + z 在n-2m-1圈后相遇
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        slow = pHead
        fast = pHead
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if slow == fast:
                fast = pHead
                while fast != slow:
                    fast = fast.next
                    slow = slow.next
                return slow
        return None