DescriptionQ299
Q299FWASIC interview problem
Find the start of a cycle
TechniquesLinked listFloyd's algorithm
DifficultyMedium
TopicLinked Lists
LanguagePython
Requirements3 checkpoints
01
Problem
Return the node where a linked-list cycle begins, or None when the list has no cycle.
Example input and output
Use this case to check your interpretationInput
1 -> 2 -> 3 -> 4, with node 4.next pointing to node 2Output
node with value 2Explanation
After the first slow/fast meeting, advancing one pointer from head and one from the meeting point finds the cycle entry.
02
Requirements (3)
- Use constant extra space.
- Do not modify the list.
- Separate cycle detection from entry discovery.