Linked List Cycle

Given the head of a linked list, determine whether the list contains a cycle — a chain that loops back on itself so traversal never terminates. The machine must answer without modifying the list and, ideally, without a visited set.

The key insight is Floyd's tortoise-and-hare: run two pointers, one moving one step per iteration and one moving two. If there is a cycle, the hare laps the tortoise and they collide — if the list ends, there is no cycle. This works because in a cycle the distance between the pointers shrinks by one each step, so they must meet within one lap.

Approach:

1. Start slow and fast at head.
2. Advance slow by one and fast by two; check for collision each iteration.
3. If fast or fast.next becomes None, return False; on collision return True.

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

Time: O(n), at most one lap before collision. Space: O(1).

Trickiest edge case: fast.next access — the loop condition must check both fast and fast.next before the two-step advance, or the machine dereferences None on an odd-length list.