前往此题

解题思路

这题也是一道非常经典的链表题，双指针伺候。

算法过程

1. 先初始化两个快慢指针slow,fast位于链表头

2. 随后将slow指针每轮走一步，fast指针每轮走两步，一直走到它们相遇，当然也会遇到无环链表，下面对两种情况进行逐个分析。

   1. 如果fast指针走到了链表的末尾not (fast and fast.next)，说明链表无环，直接返回None

   2. 如果遇到fast == slow，说明两指针相遇了。此时我们不知道两个指针在环中走了几圈，也不知道在环中走了几步，接下来我们在对这种相遇的情况进行详细分析。假设链表有a + b个节点，a指的是链表头部到环入口的节点数，b指的是链表环的节点数。

      1. 已知fast指针走的步数是slow的2倍，设两指针分别走了f,s步，记作f=2s

      2. 在相遇时fast肯定比slow多走了n圈，n未知，记作 f = s + nb -> 2s = s + nb -> s = nb, f = 2nb , 即fast走了2n环步数, slow走了n环步数。

      3. 从s = nb, 我们可以知道相遇时slow指针走了nb个步数，那么不管n为多少，它只要再走a步，必然走到了环的入口处。知道了这点我们接下来就好操作了。

         

3. 此时我们将fast指针放到链表头处，两个指针每轮走一步，直到它们相遇。此时fast指针走了a步，slow也走了a步，那么这个节点必然是环的入口。

代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head or not head.next: return None
        slow, fast = head, head

        while True:
            if not (fast and fast.next): return
            slow, fast = slow.next, fast.next.next
            if slow == fast: break
        fast = head

        while fast != slow:
            slow, fast = slow.next, fast.next
        return fast