Crack the Backend

Problem Statement

Given the head of a linked list, determine if the list has a cycle. A cycle exists if there is some node in the list that can be reached again by continuously following the next pointer (i.e. next of a node points to an earlier node). Return true if there is a cycle, false otherwise.

We cannot modify the list. O(1) extra space is required for the classic solution (Floyd's cycle detection).
If the list is empty (head == null), return false.

Key Observations

Floyd's cycle-finding (tortoise and hare): Use two pointers: slow moves one step at a time, fast moves two steps. If there is no cycle, fast will eventually hit null. If there is a cycle, slow and fast will eventually meet inside the cycle (because fast gains one step per iteration relative to slow).
So: initialize slow = fast = head. While fast != null && fast.next != null, move slow = slow.next, fast = fast.next.next. If slow == fast, return true. If the loop exits, return false.

Approach

High-level: slow and fast both start at head. Each step: slow = slow.next, fast = fast.next.next. If they meet (slow == fast), there is a cycle. If fast (or fast.next) becomes null, there is no cycle.

Steps:

slow = head, fast = head. While fast != null && fast.next != null: slow = slow.next, fast = fast.next.next. If slow == fast return true.
Return false.

Implementation

Java

public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow == fast) {
            return true;
        }
    }

    return false;
}

Test Cases

Cycle

Input

head = [3,2,0,-4], pos = 1

Expected

true

Explanation

Tail connects to node 1.

Complexity Analysis

Time: O(n).
Space: O(1).

Follow-ups

Find the node where the cycle begins (reset one pointer to head after meet).