Linked List Cycle
FreeLinked listsEasy23 of 75
The problem
Determine whether repeatedly following next pointers in a singly linked list can revisit a node. Compare node identity, not values.
Example
A → B → C → B → … has a cycle. A → B → null does not.
Need a hint?
Two runners moving at different speeds eventually meet inside a cycle.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Move slow by one link and fast by two. If they reference the same node after moving, return true. If fast or fast.next becomes null, return false. Repeated values in different nodes do not imply a cycle.
Complexity
O(n) time and O(1) space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.