判断链表是否有环（集合&快慢指针）_快慢指针判断链表是否有环

问题：给定一个链表，判断其中是否有环。(能否给出空间复杂度O(1)的解)

1.首先很容易想到的解法是利用set集合的无重复性，从表头head往后遍历，如果set集合中没有该结点则将该结点添加到集合中，如果已经存在该结点则说明有环，代码如下：

public boolean hasCycle(ListNode head) {
	if (head == null) {
		return false;
	}
	HashSet<ListNode> set = new HashSet<ListNode>();
	while (head != null) {
		if (set.contains(head)) {
			return true;
		}
		set.add(head);
		head = head.next;
	}
	return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

这种解法的空间复杂度O(n)。

2.快慢指针法，用一快一慢两指针，开始两个指针都指向链表头部。慢指针每次向前走一步，快指针每次向前走两步。如果有环，则两个指针最终一定会相遇。

关于如果有环两指针最终一定会相遇可以这样理解：它们的相对速度只差一个位置长度，快的只能一个一个位置长度的去追慢的，必然在同一个位置相遇。所以有环，快指针是一定可以追的上慢指针的。相反，如果快指针走到了表尾也就是null的位置，也说明了链表中没有环。

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

空间复杂度O(1)。