You've successfully subscribed to Nicholas Workshop
Great! Next, complete checkout for full access to Nicholas Workshop
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

Find Any Loops in Linked List

Nicholas Wong
Nicholas Wong

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
Algorithm

Nicholas Wong

Fullstack software engineer with strong background in computer science and extensive experience in software engineering and architecture. Studied in NYU, worked in Yahoo, Rakuten and Manulife.