算法——Floyd判圈算法
介绍
思想
使用快慢指针fast, slow，快指针每次走两步fast = fast.next.next，慢指针每次走一步slow = slow.next。当出现fast == null || fast.next == null时，说明链表不存在环，如果存在环，则快指针永远不可能指向null；当出现fast == slow时，说明链表存在环，此时让慢指针回到原点，然后让两个指针的速度相同，每次都只走一步fast = fast.next; slow = slow.next;，它们再次相遇的点就是环的入口。
论证
对于上面的这张图，不妨设两个指针在点R处第一次相遇，此时让慢指针回到链表头部点P处，让快慢指针同速，每次只走一步，直到第二次相遇。注意，指针在环上是逆时针走的。
第一次相遇时，有
2
t
=
s
f
a
s
t
=
∣
P
Q
∣
+
m
C
+
Q
R
⌢
2t = s_{fast} = |PQ| + mC + \overset{\LARGE{\frown}}{QR}
2t=sfast=∣PQ∣+mC+QR⌢
t
=
s
s
l
o
w
=
∣
P
Q
∣
+
n
C
+
Q
R
⌢
t = s_{slow} = |PQ| + nC + \overset{\LARGE{\frown}}{QR}
t=sslow=∣PQ∣+nC+QR⌢ 其中
s
f
a
s
t
s_{fast}
sfast是第一次相遇前快指针走的距离，
s
s
l
o
w
s_{slow}
sslow是第一次相遇前慢指针走的距离，
∣
P
Q
∣
|PQ|
∣PQ∣是点
P
P
P和点
Q
Q
Q之间的距离（也就是链表的起点到环的入口的长度），
m
m
m是第一次相遇前快指针绕环转的圈数，
n
n
n是第一次相遇前慢指针绕环转的圈数，
C
C
C是环的周长，
Q
R
⌢
\overset{\LARGE{\frown}}{QR}
QR⌢是从点
Q
Q
Q沿环逆时针到点
R
R
R的距离，
t
t
t是移动的次数（快指针每次走两步，慢指针每次走一步）。
用第一个式子减去第二个式子，得
t
=
(
m
−
n
)
C
t = (m – n)C
t=(m−n)C 再将第三个式子带入第二个式子可得
∣
P
Q
∣
+
Q
R
⌢
=
(
m
−
2
c
)
C
|PQ| + \overset{\LARGE{\frown}}{QR} = (m – 2c)C
∣PQ∣+QR⌢=(m−2c)C 也就是说
∣
P
Q
∣
|PQ|
∣PQ∣与
Q
R
⌢
\overset{\LARGE{\frown}}{QR}
QR⌢的和为环的周长的整数倍，从而可知
∣
P
Q
∣
|PQ|
∣PQ∣就是从点
R
R
R沿环逆时针到点
Q
Q
Q的距离
R
Q
⌢
\overset{\LARGE{\frown}}{RQ}
RQ⌢，即有
∣
P
Q
∣
=
R
Q
⌢
|PQ| = \overset{\LARGE{\frown}}{RQ}
∣PQ∣=RQ⌢。
现在考虑第一次相遇与第二次相遇之间的事情，慢指针从链表头部（点
P
P
P）开始遍历，快指针从第一次相遇的点（点
R
R
R）开始遍历，慢指针的路程是
∣
P
Q
∣
|PQ|
∣PQ∣，快指针的路程是
R
Q
⌢
\overset{\LARGE{\frown}}{RQ}
RQ⌢，由上面的证明
∣
P
Q
∣
=
R
Q
⌢
|PQ| = \overset{\LARGE{\frown}}{RQ}
∣PQ∣=RQ⌢可知：它们的第二次相遇点就是环的入口
Q
Q
Q。
从而当两个指针第二次相遇时，它们指向的点就是环的入口得证。
代码
对链表节点的定义如下：
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
判断链表是否有环的代码如下：
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (slow == fast) {
return true;
}
}
return false;
}
}
求环的入口的代码如下：
class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (slow == fast) {
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}
