Introduction to Fast & Slow Pointers Pattern

You are given a linked list. Decide whether it has a cycle, meaning some node's next eventually points back to a node you already visited.

The obvious approach is to remember every node you have seen. Walk the list, put each node into a hash set, and stop when you either reach the end or see a node twice. That works, and it costs O(N) extra memory.

Now think about two runners on a circular track. One runs one lap while the other runs two. If the track is a loop, the faster runner eventually catches the slower one and stands in the same place