0

Fast and slow pointers

Structuresused in ~85% of apps

Two walkers on the same track, one moving twice as fast. If the track is a loop they will meet, if it ends, the fast one gets there first. That one idea answers a whole family of questions with no extra memory at all.

Core idea. Move one pointer one step at a time and another two steps at a time. The gap between them changes by exactly one per move, and that single fact is enough to detect a cycle, find the middle, or locate the nth item from the end, in one pass, with two variables.
Playground, this isn't a screenshot
1 → 2 → 3 → 4 → 5 → back to 3
1
S F
2
3
4
5
both start at the front
1
2
S
3
F
4
5
slow +1, fast +2
1
2
3
S
4
5
F
gap is closing
1
2
3
4
S F
5
they meet. There is a loop

The gap shrinks by exactly one per move. A gap that always shrinks by one must reach zero, which is why meeting is guaranteed, not likely.

↑ play a little first, then dig in