c - 如何使用 O(N) 空间复杂度在链接列表中查找循环

Question

我知道我们可以使用两个指针并使用循环检测算法，但上周在一次采访中我被要求使用O(N) space Complexity. 怎么可能进行？

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