Linked List Cycle
Decide whether a linked list contains a cycle. (In the playground, pos is the index the last node links back to, or -1.)
A way to picture it
The tortoise and the hare race along the track. On a straight road the hare just reaches the finish. But if the road secretly loops back, the hare laps around and eventually lands right on top of the tortoise.
How to approach it
Move slow 1 step and fast 2 steps. If fast hits null there's no cycle; if they ever meet, there is one.
Example
Input: {"head":[3,2,0,null],"pos":1}. Output: true.
Complexity: O(n) time and O(1) space. Inside a loop the gap closes by one node per step.
This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.