employer cover photo
employer logo
employer logo

Sandia National Laboratories

Engaged Employer

Sandia National Laboratories Interview Question

How can you detect a cycle in a linked list using only constant space and linear time?

Interview Answer

Anonymous

Feb 27, 2021

I caught a break with the question. I had previously been an instructor at the university level in computer science and had used the question in assignments for my students. In addition, my graduate study had focused on garbage collection, where the problem naturally arises. The answer is generally known as Floyd's Tortoise and Hare Algorithm. Use two pointers to advance down the list at different rates. If the fast pointer reaches the end, there is no cycle. If the fast pointer detects the slow pointer in front of it, there is a cycle. You further detect the size of the cycle by setting the pointers to the same node after detecting a cycle and cycling one around the list one node at a time until the other pointer is found giving the length of the cycle. The starting point of the cycle can be found be setting both pointers to the start of the list, advancing one for the length of the list, and advancing both until the are equal, which is the point where the cycle starts.