Cycles & the middle node

Fast and slow pointers (Floyd's tortoise and hare) walk the same list at different speeds. On a list without a cycle, the fast pointer reaches the end after about n / 2 of its moves, at which point the slow pointer has covered half the list: it is at the middle.

If the list has a cycle, the fast pointer never reaches the end. Once both pointers are inside the loop, the fast one gains one node per step, so it must land on the slow one within one lap. With a little arithmetic, the meeting point also leads you to the node where the cycle begins.

The alternative, storing every visited node in a hash set, is also O(n) time but needs O(n) memory. Floyd's method needs only two pointers.

1. 1Set slow = fast = head. Loop while fast and fast.next exist: slow = slow.next, fast = fast.next.next.
2. 2Middle: when the loop ends, slow is the middle. For even length (for example 4 nodes), this version returns the second middle; start fast at head.next to get the first middle instead.
3. 3Cycle detection: if at any point slow is fast (the same node), there is a cycle. If fast reaches None, there is none.
4. 4Why they meet: once both are in a cycle of length L, the gap between them shrinks by exactly 1 per step, so it reaches 0 in fewer than L steps. Total time is O(n).
5. 5Cycle start: let a be the distance from head to the cycle start and b the distance from the start to the meeting point. Fast travelled twice as far, so 2(a + b) = a + b + kL, which gives a = kL - b. Walking a steps from the meeting point therefore lands exactly on the cycle start.
6. 6So reset one pointer to head, keep the other at the meeting point, and move both one step at a time; the node where they meet is the start of the cycle.

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

def cycle_start(head):
    """Return the node where the cycle begins, or None if there is no cycle."""
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:                  # they met inside the cycle
            p = head
            while p is not slow:          # both move 1 step; they meet at the start
                p, slow = p.next, slow.next
            return p
    return None                           # fast fell off the end: no cycle

def middle_node(head):
    """Middle node; for even length returns the second of the two middles."""
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow

cycle_start first detects a meeting point, then uses the a = kL - b result to walk a fresh pointer from the head in step with the meeting pointer. middle_node is the same loop without the meeting check. Both are O(n) time and O(1) space. Use 'is' to compare node identity, not values.

Cost: O(n) time, O(1) space. The hash-set alternative is O(n) time and O(n) space.