[LeetCode 141] Linked List Cycle

Question

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

Stats

Adjusted Difficulty	4
Time to use	--------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is an famous question, historically know as the Tortoise and hare.

Solution

This blog has a great solution.

Use fast and low pointer. The advantage about fast/slow pointers is that when a circle is located, the fast one will catch the slow one for sure.

Code

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null)
		return false;
	ListNode first = head.next, second = first.next;
	while (first != null && second != null) {
		if (first == second) return true;
		first = first.next;
		second = second.next;
		if (second == null) return false;
		second = second.next;
	}
	return false;
}