Fast and slow to the middle
Updated
Both start at head. While fast and fast.next: slow = slow.next, fast = fast.next.next. When fast cannot take two steps, slow is at the middle.
What to focus on
Odd n: slow lands on the unique mid. Even n: slow lands on the second mid (or first, if you stop one step earlier — pick a rule). n = 1 is already the mid.
Worked examples
odd
a = [4, 1, 9] as 4→1→9- slow 4→1, fast 4→1→9
- fast.next is null, stop
Result: slow at 1, mid
one
a = [7] as 7→null- fast.next null immediately
- zero loop iterations
Result: slow at 7
even
a = [4, 1, 9, 1] as 4→1→9→1- round 1: slow 1, fast 9
- round 2: slow 9, fast null
Result: slow at 9, second mid
Try it
Write middle(a). a is the start of an acyclic list. slow moves one next. fast moves two. Return the middle node. Even n uses the second mid. 4→1→9 mid is 1. 7 is 7. 4→1→9→1 second mid is 9.
The list is nonempty and acyclic.