Fast and Slow Pointers

Fast/slow pointers (Floyd's): fast moves $2\times$ slow's speed.

Cycle detection:

slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow == fast: return true
return false

Why it works: In a cycle, fast laps slow. Distance decreases by $1$ each step.

Middle of list: When fast reaches end, slow is at middle.

Time: $O(n)$. Space: $O(1)$.