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
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: