题目：判断给定的链表中是否有环。如果有环则返回true，否则返回false。你能给出空间复杂度O(1)的解法么？

Leetcode在线OJ系统：传送门

示例1：

1
2
输出：true
解释：链表中有一个环，由 -4 指向 2

示例2:

1
2
输出：`true`
解释：链表中有一个环，由 2 指向 1

示例3：

1
2
输出：`false`
解释：链表中没有环

思路：将链表想象成校园里的操场，两位同学从同一起点开始比赛跑步，出发后，如果两位同学的跑步速度不一致，那么跑过若干圈后，他们一定会在跑道的某处相遇，且跑的快的同学恰好比跑的慢的同学多跑一圈。这是物理运动学上的经典追击问题。

对于链表来说，我们可以定义一快一慢两个指针，让它们同时从头节点同时出发，快指针每次走两步，慢指针每次走一步，如果它们最终能在某处“相遇”，说明链表有环，如果快指针走到链表末尾都没有追上走的慢的指针，说明链表无环。

以上的思路俗称：“快慢指针法”；学名：Floyd判圈算法。

Floyd判圈算法（Floyd Cycle Detection Algorithm），又称龟兔赛跑算法(Tortoise and Hare Algorithm),是一个可以在有限状态机、迭代函数或者链表上判断是否存在环，以及判断环的起点与长度的算法。

Java语言实现如下：

单链表节点类定义可查看文章：数据结构之链表-基础知识

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static boolean hasCycle(SinglyLinkedListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    SinglyLinkedListNode fast = head;
    SinglyLinkedListNode slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            return true;
        }
    }
    return false;
}