How are loops detected in a linked list?

Loops in a linked list are detected using two pointers moving at different speeds, often called the 'tortoise and the hare' method.

In more detail, the 'tortoise and the hare' method involves two pointers, one moving twice as fast as the other. If there is a loop in the linked list, the faster pointer, or 'hare', will eventually meet the slower pointer, or 'tortoise'. This is because the 'hare' will enter the loop first, and as it continues to move around the loop, the 'tortoise' will also enter the loop. Since the 'hare' is moving at twice the speed, it will eventually catch up to the 'tortoise' from behind, indicating that a loop exists.

To implement this, you would initialise two pointers at the start of the linked list. In each iteration of a loop, you move the 'tortoise' pointer one step and the 'hare' pointer two steps. If at any point the two pointers meet, you can conclude that a loop exists in the linked list. If the 'hare' pointer reaches the end of the linked list (i.e., it becomes null), then there is no loop.

This method is efficient because it only requires a single pass through the linked list, making it a linear time complexity solution, O(n), where n is the number of elements in the linked list. It's also worth noting that this method doesn't require any extra space, so it's a constant space complexity solution, O(1).

However, it's important to handle the case where the linked list is empty or only contains a single element. In these cases, you should return that no loop exists. Also, be careful to always check if the 'hare' pointer and its next pointer are not null before moving it two steps forward to avoid a null pointer exception.