Detecting a Loop in a Singly Linked List | LeetCode

This is one of the most common interview questions asked during a technical interview. I call it the classic linked list question.

The naive approach requires O(N^2) time and O(N) space. Basically you store all visited nodes, and compare each of them while traversing each node.

Hint: The best approach uses only O(N) time and O(1) space. Remember my previous post? Try to use two pointers to traverse the list.

Solution:
The best solution runs in O(N) time and uses O(1) space. It uses two pointers (one slow pointer and one fast pointer). The slow pointer advances one node at a time, while the fast pointer traverses twice as fast. If the list has loop in it, eventually the fast and slow pointer will meet at the same node. On the other hand, if the loop has no loop, the fast pointer will reach the end of list before the slow pointer does.

Read full article from Detecting a Loop in a Singly Linked List | LeetCode