Find Any Loops in Linked List

Question

Validate a linked list whether there is a loop in it. That is, there is a node in a linked list with the next pointer pointing to a node ahead in the same linked list. This is the question I encountered in 2013 spring, from a Yahoo phone interview.

Solution

Define 2 pointers pointing to the head of the linked list. Then we move the pointers at different speed. For example, move 1 step for pointer 1 every time, but 2 steps for pointer 2. Test to see if they point to the same element. If so we got a loop. If not, repeat until you find a loop or you reach the end of the list.

loop slow = slow->next fast = fast->next->next