• The number of the nodes in the list is in the range [0, 10,000]
• -100,000 <= Node.val <= 100,000
• Can you solve it using O(1) memory?

We are handed a singly linked list, and we need to determine if it contains a cycle—a loop where a node points back to a previously visited node, causing any traversal to get trapped in an infinite loop. In an ordinary list, we eventually fall off the end when we reach a null pointer. But in a cyclic list, we could walk forever without ever finding an end. How can we detect if a list is an endless loop without getting stuck in it ourselves?

The most intuitive way to spot a loop is to keep track of where we have already been. As we travel down the list, we drop a memory breadcrumb by storing the unique address of each visited node in a hash set. At each new node, we look down at our records. If we ever step onto a node that is already in our set, we have found the entrance to the loop and can confidently confirm that a cycle exists.

While this works, it requires O(N) memory to store every visited node. If the list is massive, tracking thousands of breadcrumbs is a high-cost memory tax.

# Save visited node addresses to a set
seen = set()
curr = head

while curr:
    if curr in seen:
        return True  # Already been here! Loop detected.
    seen.add(curr)
    curr = curr.next

return False  # Fell off the end, no cycle.

To eliminate the memory tax entirely, we can detect cycles using two coordinated pointers moving at different speeds down the track. Each pointer has a strict contract:
- The Slow Pointer (slow): Advances steadily, taking exactly one node per step.
- The Fast Pointer (fast): Sprints ahead, taking exactly two nodes per step.

Both start together at the head of the list.

Think of this like two runners on a track. If the list is a straight line, the sprinter (fast) will reach the end of the track and stop, while the jogger (slow) is still halfway.

However, if the track has a circular loop, the sprinter is trapped in the circle and will keep running forever. Because the sprinter moves twice as fast, it will gradually catch up to the jogger from behind. At every step, the distance between them shrinks by exactly one node. No matter how large the loop is, the sprinter is mathematically guaranteed to "lap" the jogger, colliding on the exact same node.

We advance both pointers in synchronized strides. If the fast pointer or its next node becomes null, we know the list has a definite end and contains no cycle. But if the pointers ever meet at the exact same physical node address, we have detected a collision and proven a cycle exists.

slow = head
fast = head

# Traverse until the sprinter runs out of track
while fast and fast.next:
    slow = slow.next      # Jogger moves 1 step
    fast = fast.next.next # Sprinter moves 2 steps
    
    # If they occupy the exact same physical address, a cycle exists
    if slow == fast:
        return True

return False # Sprinter safely reached the end of the line

This zero-memory approach handles small lists cleanly without crashing:
- Empty List (head is null): The while loop condition checks fail immediately. We exit and return false.
- Single-Node List (no cycle): fast.next is null from the start. We exit immediately and return false.
- Self-Loop (single node pointing to itself): slow steps to Node 1, and fast steps twice (which, due to the self-loop, lands back on Node 1). They collide immediately on the first step.