This is similar to Tortoise and Hare Algorithm, as it also involves slow and fast moving pointers. Starting at the head, when the fast pointer reaches the end of the list, the slow pointer will be at the middle.
Even Length List
0 -> 1 -> 2 -> 3
| Slow | Fast |
|---|---|
| 0 | 0 |
| 1 | 2 |
| The algorithm terminates as the fast pointer can’t move forward. The slow pointer points at 1 middle. It can be incremented if the other is required. |
Odd Length List
0 -> 1 -> 2 -> 3 -> 4
| Slow | Fast |
|---|---|
| 0 | 0 |
| 1 | 2 |
| 2 | 4 |
| Here the correct middle is found. |