环路检测
题目描述 算法思想 这道题需要用到额外空间进行求解的方法这里就不再赘述，这里主要讲述空间为O(1)的方法。 这里介绍一个大佬的思想，其链接我放在最后。
1、我们可以先利用快慢指针，来判断该链表是否有环，如果有环，则最后快慢指针会在环中相遇。
2、这里根据图，我们假设相遇点在c。
3、则令起点a到b的距离为m，b点到相遇点的距离为y，并且假设环的长度为n。
4、则有，慢指针走到相遇点的路程为m+y。快指针走到相遇点的距离是m+y+xn（其中x代表快指针走的在环种可能走的圈数）。
5、因为我们快指针的速度设定为慢指针速度的两倍。所以有关系2*(m+y)=m+y+xn。以此，推导出，m+y=xn。
6、继续对等式移项，有m=(x-1)n+(n-y)。也就是，快指针只要再移动m的距离就能从c点移到b点，并且这段距离与从a点到b点的距离相等。
7、所以只要将一个指针移到起点，并且两个指针都以单步移动的模式，其终能在b点相遇，也就是环的起点。 代码实现
# 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: p = q = head while q and q.next: p = p.next q = q.next.next if p == q: break if not q or not q.next: return None p = head while p != q: p = p.next q = q.next return p这是作者
作者：chen-hui-d 链接：https://leetcode-cn.com/problems/linked-list-cycle-lcci/solution/kuai-man-zhi-zhen-zheng-ming-bi-jiao-yan-jin-by-ch/ 来源：力扣（LeetCode）
