Solution to Leetcode 141: Linked List Cycle

In this classic exercise, we need to return if the linked list contains a cycle.

Naive algorithm

The most natural wai of solving the problem is to track all encoutered node in a Set, or a similar data structure, and return false if we encounter an element twice:

public boolean hasCycle(ListNode head) {
    Set<ListNode> set = new HashSet<>();
    while (head != null) {
        if (set.contains(head)) {
            return true;
        }
        set.add(head);
        head = head.next;
    }
    return false;
}

The algorithm is O(n) in time and space.

O(1) space algorithm

9 out of 10 times, the follow-up question if you used the naive algorithm will be to sove it in O(1) space. Then if you have seen this trick before it will be easy, otherwise it might be hard to come up with.

We use a fast pointer and a slow pointer. At each iteration, the fast pointer advances by 2 steps, and the slow one advances by 1 step. If there is a cycle there will be a time where fast catches up with slow and fast == slow. Otherwise, fast will be null at the end of the list.

Code

public boolean hasCycle(ListNode head) {
    if (head == null) {
        return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while(slow != fast && fast != null) {
        slow = slow.next;
        fast = fast.next;
        if (fast != null) {
            fast = fast.next;
        }
    }
    return (slow == fast);
}

Time and Space complexity

This is O(n) in time and O(1) in space complexity.