Find Out if a Linked List has a Cycle

Without marking nodes, find out if a linked list has a cycle in it or not.

2026 Update: Floyd’s Cycle Detection — Tortoise and Hare

Detecting a cycle in a linked list is solved by Floyd’s algorithm (tortoise and hare): two pointers at different speeds. If there’s a cycle, the fast pointer eventually laps the slow pointer. If not, the fast pointer reaches null.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Level 1: Detect if cycle exists — O(n) time, O(1) space
def has_cycle(head: ListNode) -> bool:
    """Floyd's cycle detection: slow moves 1 step, fast moves 2 steps."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

# Level 2: Find the START of the cycle — key insight
def detect_cycle_start(head: ListNode) -> ListNode:
    """
    After slow and fast meet:
    Reset one pointer to head, keep other at meeting point.
    Both advance one step at a time → they meet at cycle start.

    PROOF: If head→cycle_start = F steps, cycle_start→meeting = a steps,
    cycle length = C. Then: slow traveled F+a, fast traveled F+a+C (one full loop).
    Since fast = 2×slow: F+a+C = 2(F+a) → C = F+a → F = C-a.
    So moving F steps from head = moving C-a steps around cycle from meeting point
    = arriving at cycle start.
    """
    slow = fast = head
    # Phase 1: find meeting point
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None  # No cycle

    # Phase 2: find cycle start
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    return slow

# Level 3: Find cycle length
def cycle_length(head: ListNode) -> int:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            # Count steps around cycle
            count = 1
            fast = fast.next
            while fast != slow:
                fast = fast.next
                count += 1
            return count
    return 0

# Build a list with a cycle for testing
def build_cyclic_list(values, cycle_pos):
    """cycle_pos: index of node where tail connects back to (-1 for no cycle)."""
    nodes = [ListNode(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i+1]
    if cycle_pos >= 0:
        nodes[-1].next = nodes[cycle_pos]
    return nodes[0] if nodes else None

# Test
head = build_cyclic_list([3, 2, 0, -4], cycle_pos=1)  # Tail → node at index 1
print(has_cycle(head))           # True
start = detect_cycle_start(head)
print(start.val)                 # 2 (value at cycle start)
print(cycle_length(head))        # 3 (2→0→-4→2)

Applications of cycle detection beyond linked lists:

• Functional graph cycles: Finding cycles in functions f: S→S (e.g., hash collisions)
• Rho algorithm: Pollard’s integer factorization uses Floyd’s cycle detection
• Happy number: LeetCode #202 — cycle detection in digit-square sequences
• Find duplicate in array: LeetCode #287 — treat array as linked list with cycles

LeetCode #141 (Linked List Cycle), #142 (Linked List Cycle II). The cycle-start proof via the F = C-a relationship is a common “explain the math” follow-up.

function hasCycle(head) {
    if (!head || !head.next) return false;

    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next;          // Move 1 step
        fast = fast.next.next;     // Move 2 steps

        if (slow === fast) {
            return true;  // Cycle detected!
        }
    }

    return false;  // Fast reached end, no cycle
}

// Test with cycle
let node1 = { val: 1, next: null };
let node2 = { val: 2, next: null };
let node3 = { val: 3, next: null };
let node4 = { val: 4, next: null };

node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node2;  // Creates cycle

console.log(hasCycle(node1));  // true

// Test without cycle
let listNoCycle = { val: 1, next: { val: 2, next: null } };
console.log(hasCycle(listNoCycle));  // false

function detectCycle(head) {
    if (!head || !head.next) return null;

    let slow = head;
    let fast = head;

    // Phase 1: Detect if cycle exists
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow === fast) {
            // Cycle detected!
            // Phase 2: Find start of cycle
            slow = head;

            while (slow !== fast) {
                slow = slow.next;
                fast = fast.next;
            }

            return slow;  // This is the cycle start
        }
    }

    return null;  // No cycle
}