What is the extra space required by Floyd’s cycle-detection algorithm on a linked list of n nodes?
Correct answer A. O(1)
Explanation
Floyd's algorithm uses only two pointers, slow and fast, no matter how long the list is, so its extra space is constant. The alternative approach of storing every visited node in a hash set also finds cycles in O(n) time but needs O(n) extra memory. That memory saving is why Floyd's technique is the standard answer in interviews and exams.
Answer checked How we write and check questions
Discussion