*Find if a linked list has a cycle given a pointer to it's first element.*

There are several ways of solving this problem.

- iterate over the list and insert elements into a hash table. We have a cycle if we insert the same element twice. This solution requires
**0(n)**time and**0(n)**memory. - adapt the list to this particular situation. Insert a field that marks the node as visited or not. This solution has the drawback of modifying the list which is not always possible.
- Floyd algorithm which will be presented below its an efficient and easy to understand algorithm and requires
**O(n)**time and**O(1)**additional memory.

Also known as the tortoise and hare algorithm it uses two pointers a and b , where a moves two times faster than b.

The pseudocode for the algorithm is as follows:

a <- list_head

b <- list_head

do

a <- a.next.next

b <- b.next

while a <> b

//if there is a cycle then a will be equal at some point with b.

An immediate application of Floyd's algorithm is retrieving the element in the middle of a list without computing it's length.

## No comments:

Post a Comment