Linked List Cycle Detection (Fast and Slow Pointers)

Problem Statement

Given the head of a linked list, determine whether the list has a cycle (a node whose next points back to an earlier node).

Example

Input:  3 -> 2 -> 0 -> -4 -> (back to node 2)
Output: true

Two Pointer Approach

Use Floyd’s Tortoise and Hare. Move slow one step and fast two steps at a time. If there is a cycle, the fast pointer eventually laps and meets the slow pointer; if fast reaches the end, there is no cycle.

Complexity

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

Solution Code

Python

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

Java

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

C++

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

Key Takeaways

• Fast moves 2x, slow moves 1x — they can only meet inside a cycle.
• O(1) space beats the hash-set approach.
• Extending this (reset one pointer to head) finds the cycle’s start node.