题目链接：https://leetcode-cn.com/problems/linked-list-cycle-ii/
难度：中等

描述：
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

提示：
链表节点数：[0, 10000]

题解

思路：
维护两个指针fast和slow，slow每次走一步，fast每次走两步。
若链表中没有环，那么fast最终会等于None。
若链表中有环，那么slow和fast必定会相遇。这时设slow走过的步数为x，那么fast走过的步数就为2x。设链表头节点到环的入口的步数为a，环的长度为b，slow比fast多走n个环，即2x - x = nb，即x = nb。这时，只要fast或slow再走a步就又到了环的入口，所以我们可以将fast移动到head处，让它每次走一步，slow也同时行动。那么fast走a步到了环的入口时，slow也走了a步到了环的入口，它们相遇，就可以找的环的入口了。

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.next = None
  7. class Solution:
  8.     def detectCycle(self, head: ListNode) -> ListNode:
  9.         slow, fast = head, head
  11.         while fast is not None and fast.next is not None:
  12.             fast = fast.next.next
  13.             slow = slow.next
  15.             if fast == slow:
  16.                 slow = head
  17.                 while fast != slow:
  18.                     fast = fast.next
  19.                     slow = slow.next
  20.                 return slow
  22.         return None