Test for cyclicity

**lgtout** · November 9, 2017, 7:18pm

[EPIJ v 1.6.1 problem 8.3]

I have a solution that detects the presence of a cycle. Is it possible to find the start node of the cycle in better than O(n) space?

**tsunghsienlee** · November 10, 2017, 3:48am

Hint: You can try to use the solution of overlapping list.

**lgtout** · November 14, 2017, 11:35pm

is that a “yes” to my question?
Can it be done in O(1) space?
Also, does the problem allow for being destructive of the list, in order to find the start node of the cycle?
For instance, would it be allowed for me to break the cycle?

**lgtout** · November 15, 2017, 11:06pm

Never mind. I have a solution now. For others with the same question: Yes, it’s possible to find the start node of the cycle in O(1) space and without modifying the list.