Linked List Cycle
Linked List Cycle is an easy Linked List problem from the Blind 75. The key pattern is fast and slow pointers, and a good solution runs in O(n) time.
Problem
Given node values and a zero-based tail link position (-1 for none), determine whether the represented list contains a cycle.
Examples
Example 1
Input
{"values":[2,5,9],"tailTo":0}Output
trueExample 2
Input
{"values":[6,1,8,-3],"tailTo":2}Output
trueExample 3
Input
{"values":[1],"tailTo":-1}Output
falseApproach
Move one pointer one step and another two steps at a time. They meet only if the list loops back on itself.
| Pattern | Fast and slow pointers |
|---|---|
| Time | O(n) |
| Space | O(1) |
Watch out for
Here the cycle is given as a tail link position; -1 means the list ends normally.