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.