Finding the Middle

To find the middle node:

slow = head
fast = head
while fast != null and fast.next != null:
    slow = slow.next
    fast = fast.next.next
return slow

For odd-length lists, slow points to the exact middle. For even-length lists, it points to the second of the two middle nodes.

If you need the first middle node for even-length lists, check fast.next != null and fast.next.next != null instead.

Why is this useful? Many problems require processing the two halves of a list separately. Finding the middle in $O(n)$ time and $O(1)$ space enables this without converting to an array first.