[LeetCode 141] Linked List Cycle

Question

link

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;
}