Interview Practice Extra 01 – Find Loop 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

Leave a Reply

%d bloggers like this: