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

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        # 步骤1：检测环并返回相遇点
        meet_node = self.detect_loop(pHead)
        if not meet_node:
            return None

        # 步骤2：寻找环的入口
        slow = pHead
        fast = meet_node
        while slow != fast:
            slow = slow.next
            fast = fast.next

        return slow

    def detect_loop(self, head):
        """检测链表中是否存在环，存在则返回相遇点，否则返回None"""
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return slow  # 返回相遇点
        return None  # 无环