0

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?

coder
  • 183
  • 9
  • 2
    [Tortoise and the Hare Algorithm](http://stackoverflow.com/questions/494830/how-to-determine-if-a-linked-list-has-a-cycle-using-only-two-memory-locations) – Dayal rai Jul 05 '13 at 11:00
  • 3
    Your two pointer algorithm is O(1) space, so it is already O(N) space. – Theodore Norvell Jul 05 '13 at 11:00
  • @TheodoreNorvell I was going to suggest the very same, but wasn't sure. Good to know I was right. –  Jul 05 '13 at 11:01

1 Answers1

1

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.)

Community
  • 1
  • 1
phoeagon
  • 2,080
  • 17
  • 20