Introduction to Fast & Slow Pointers Pattern

You are given a linked list. Your task is to decide whether the list contains a cycle.

A linked list contains nodes. Each node has a value and a next reference to another node.

Normally, following next eventually reaches the end of the list. In a cycle, one node points back to an earlier node. Following next then continues forever.

A simple solution remembers every node that you visit:

1. Create an empty hash set.
2. Walk through the list.
3. Add each node to the set.
4. If a node is already in the set, the list has a cycle.

This solution takes O(N) time and O(N) extra space.