Linked List Cycle

Detect whether a list loops back on itself, in O(1) space. Move slow one step and fast two steps. If there's a cycle, fast laps slow and they meet; otherwise fast reaches null.

Traced input: head = [3, 2, 0, -4], tail links to index 1 → true. Original problem: neetcode.io/problems/linked-list-cycle-detection

Complexity

Once both are in the cycle, the gap closes by one each step.

Key idea

• In a cycle, the faster runner must eventually catch the slower one.
• Each step, the distance between them shrinks by exactly one, so fast can't jump over slow.
• Check fast != null && fast.next != null before moving fast.

Common mistakes

• A HashSet of visited nodes works but uses O(n) space.
• Checking slow == fast before the first move (they start equal).
• Forgetting fast.next != null and crashing on even-length lists.

Solution

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

def hasCycle(head: Optional[ListNode]) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

bool hasCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

Edge cases

Each one has its own trace in the interactive view.