题目:判断给定的链表中是否有环。如果有环则返回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;
}