## Coding Interview 7: Determining Cycles in a Linked List

Post by: Blake
Posted on: 11 Vigeo 7:0 - 1.5.7
How do you know if a linked list has a cycle in it? As in, one of the nodes in the linked list points to a previous node in the list.

This is another one of those cliche interview questions that tends to come up very frequently. Although interviewers are probably catching on now, and it's starting to phase out again. It's still a good one to know, though.

Create a hash table. Start traversing the list. Put each node in the hash table as you find it. If the node already exists in the hash table, then booya.

This wastes a ton of memory if the list is large.

## The Good Solution

(Also known as: Floyd's Cycle Finding Solution)
Iterate through the list with two different iterators. Let's call them iterator A and iterator B. At each step, check to see if the iterators are pointing at the same node. Then increment the B iterator, but not the A one. Check again.

Imagine a road leading up to a roundabout. Two cars drive on the road to the roundabout and then circle around inside it indefinitely. If one car is driving twice as fast as the other, they will eventually crash into each other.

On the other hand, if there is no roundabout, and the road just goes into a brick wall, the faster car will crash into the wall instead.

if linked_list_node == null: return false // list is empty!