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

# -*- 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
        # 标记该链表是否有环。
        is_circular = False
        # 用快慢指针找到环中的一个节点，判断一下fast.next是为了防止fast.next.next出现越界。
        while slow and fast and fast.next:
            # 慢指针每次走一步。
            slow = slow.next
            # 快指针每次走两步。
            fast = fast.next.next
            if slow == fast:
                is_circular = True
                break
        
        # 遍历原始链表和环(此处的环内节点可以用slow和fast任意一个来表示)，公共节点的头节点就是环的入口。
        while pHead and slow and is_circular:
            if pHead != slow:
                pHead = pHead.next
                slow = slow.next
            else:
                return pHead
        
        return None