I know that we can use two pointers and using cycle detection algorithm but last week in an interview I was asked to do the same by using O(N) space Complexity. How can proceed?
-
2Tortoise and the Hare AlgorithmDayal rai– Dayal rai2013-07-05 11:00:21 +00:00Commented Jul 5, 2013 at 11:00
-
3Your two pointer algorithm is O(1) space, so it is already O(N) space.Theodore Norvell– Theodore Norvell2013-07-05 11:00:27 +00:00Commented Jul 5, 2013 at 11:00
-
@TheodoreNorvell I was going to suggest the very same, but wasn't sure. Good to know I was right.user529758– user5297582013-07-05 11:01:36 +00:00Commented Jul 5, 2013 at 11:01
Add a comment
|
1 Answer
For detailed implementation, read this post(How to determine if a linked list has a cycle using only two memory locations).
Basically you maintain two pointers, both of which point at the head of the linked list initially. On each enumeration, advance the first pointer by one node and the other by two. If at some point these two pointers reach an identical node again, a cycle is detected.
I gather from your description that you do know this algorithm. If the space taken by the linked list itself is not considered, this one works in O(1) space. And even with that much space considered, it's still O(n). (If space complexity is the only concern, obviously worse algorithm exists.)
