总集篇：环形链表（是否成环？环长度？入环点？）

LeetCode 141. 环形链表
LeetCode 142. 环形链表 II

弗洛伊德判圈算法
Brent’s Cycle Detection Algorithm的时间复杂度在常数上比弗洛伊德判圈算法更小。
本文基于弗洛伊德判圈算法展开。

给定一个链表，回答三个问题：

1. 链表中是否有环，返回一个布尔值，true表示有环，false表示无环。
2. 链表中环的长度是多少，返回一个整数表示环上的结点数，无环返回0。
3. 链表中在可以通过next第二次到达的第一个结点，无环返回空引用。

回答：
4. 有环，返回true。
5. 长度为3，返回3.
6. 通过无限next可以第二次到达的结点中第一个是第二个结点，返回该结点的引用。

本质上弗洛伊德判圈算法就是利用了快慢指针。

问题一：链表中是否有环，返回一个布尔值，true表示有环，false表示无环。
快慢均从头结点出发，慢指针每次走一步，快指针每次走两步，只要有一个指针指向空，说明链表无环，只要两者可以指向同一个结点则说明链表有环。
为什么快慢指针指向同一个结点可以说明有环？我们就来讨论一下有环的情况。
首先，快指针一定比慢指针先到环上。
其次，等慢指针第一次到环上时，快指针一定还在环上且走了若干步，有可能绕了好几圈，不过这不重要，由于是一个环，所以快慢指针是一个相对位置，我们可以认为慢指针在快指针之前，这样就是每次移动，快指针会距离慢指针近一步，则两者一定会相遇。

问题二：链表中环的长度是多少，返回一个整数表示环上的结点数，无环返回0。
在问题一的基础上，当两者相遇时，只需让任意一个指针以每次一步绕一圈再次与另一个指针重合即可，使用一个计数器即可记录步数。

问题三：链表中在可以通过next第二次到达的第一个结点，即入环点，无环返回空引用。
在第一个问题的基础上，当两者相遇时，有这么一个规律，利用这个规律可以很容易求出要求的结点。下面解释一下：
显然，有环链表可以分为非环部分和环部分，假设非环部分需要走a步（最后一步恰好走到环上，假设该点为D，D就是所求点），环部分走一圈需要走b步，显然a+b为结点数之和。
考虑相遇时的情况：当相遇时快慢指针首先一定都走过了非环部分（a步），其次都会绕环走若干圈，慢指针最少是0圈，设为k1，快指针至少是1圈，设为k2，由于一定是快指针先到环上且随后需要追上慢指针，所以k1<k2，最后，相遇的点不一定在哪，有可能快慢指针正好走完完整的环后在D相遇，有可能两者在中途相遇，就是一个不完整的环，假设这一部分不完整的环走的步数为c，这个不完整的环显然两者都是要走的，快慢指针唯一的区别在于两者在环上循环的圈数不同。

由此：
慢指针走的步数$S_1=a+k_1\ast b+c$
快指针走的步数$S_2=a+k_2\ast b+c$
由于两者走的次数一样，仅仅每次步数不一样，所以$2S_1=S2$，即：
$$\begin{array}{r}2\ast (a+k_1\ast b+c)=a+k_2\ast b+c\\ a+c=(k_2-2k_1)b\\ a=(k_2-2k_1)b-c\end{array}$$
$k_2-2k_1$一定是一个正整数，无论其值是多少，(k_2-2k_1)b永远都是完整绕圈走的步数，哎，这时不妨考虑一下-c当一圈中去掉c这一部分之后，恰好是从相遇点走到所求点D点的步数。也就是说从相遇点走到所求点D点再绕$k_2-2k_1-1$圈环回到D就相当于从头结点走到所求点D，两者步数相同。
得出这个规律后就好说了，只需要让一个指针从头结点出发，另一个指针从相遇的结点出发，当第一次相遇时一定会相遇再所求点D。

代码实现

from typing import Optionalclass ListNode:def __init__(self, x):self.val = xself.next = Noneclass Solution:def has_cycle(self, head: Optional[ListNode]) -> bool:slow = fast = headwhile True:if not slow:return Falseslow = slow.nextif not fast or not fast.next:return Falsefast = fast.next.nextif slow == fast:return True# 时间复杂度O(n)：时间复杂度与走的次数成正相关，慢指针每次走一步，我们考虑慢指针走的次数，当没有环时，走的次数一定不大于n，当有环时，会走一个非环部分a，然后快指针追慢指针，环部分总共b步，所以以一定会在b步以内快指针能追上慢指针，由于a+b=n，所以整个算法时间复杂度为O(n)。# 空间复杂度O(1)：未使用额外空间。def cycle_len(self, head: Optional[ListNode]) -> int:slow = fast = headwhile True:if not slow:return 0slow = slow.nextif not fast or not fast.next:return 0fast = fast.next.nextif slow == fast:break# 相遇后，随便一个指针绕一圈再重合就行，这里让快指针按照每次一步绕一圈length = 1fast = fast.nextwhile slow != fast:fast = fast.nextlength += 1return length# 时间复杂度O(n)：相遇部分耗时O(n)级别，再绕一圈统计环长度b，显然还是O(n)。# 空间复杂度O(1)：未使用额外空间。def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:slow = fast = headwhile True:if not slow:return Noneslow = slow.nextif not fast or not fast.next:return Nonefast = fast.next.nextif slow == fast:break# 相遇后，让快指针再次从head出发每次一步，同时慢指针也每次走一步，两者随后第一次相遇点即为所求点# 其实不太好理解的是这一部分，前面两个函数都好理解fast = headwhile fast != slow:fast = fast.nextslow = slow.nextreturn fast# 时间复杂度O(n)：相遇部分耗时O(n)级别，在走一个非环部分a，显然还是O(n)。# 空间复杂度O(1)：未使用额外空间。a, b, c, d = ListNode(3), ListNode(2), ListNode(0), ListNode(-4)
a.next = b
b.next = c
c.next = d
d.next = bassert Solution().has_cycle(a)
assert Solution().cycle_len(a) == 3
assert Solution().detectCycle(a) is b