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

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        slow = self.hasCycle(pHead)
        if slow == None:
            return None
        fast = pHead
        while fast!= slow:
            fast = fast.next
            slow = slow.next
        return slow
    
    def hasCycle(self,head):
        if head == None:
            return None
        fast = head
        slow = head
        while fast!=None and fast.next!=None:
            fast = fast.next.next
            slow = slow.next

            if fast == slow:
                return slow
        return None
        

这道题可以看作是判断链表中是否有环的进阶版本，寻找环的入口节点

1. 解题思路的话，首先要先判断，这个链表有没有环，然后再寻找环入口节点，所以第一步是先写一个判断是否有环的函数
2. 如果有环的话，那接下来就是找第一个节点数，这里很复杂，基本是通过计算步长的方式发现的一个规律
3. 规律就是如果在环的相遇点，slow指针位置不变，将fast指针挪动到链表第一位，这个时候再次同时移动双指针，他们下一次相遇的位置，就是链表的头节点（具体怎么算的，还没搞的特别明白，第一次刷，先记住。。）
4. 所以上一个函数判断是否有环以后，需要返回none(无环)或者slow的位置（有环）
5. 然后此时将fast指针指向头节点，再次依次向后移动，取fast=slow时的节点，return即可