Length Of A Cycle

July 21, 2017

Our exercise today is about finding cycles in a linked list. We’ve seen algorithms due to Robert Floyd (the tortoise-and-hare algorithm) and Richard Brent (the power-of-two algorithm) in previous exercises, but in those cases all we were interested in doing was in finding a cycle if it existed. In today’s exercise we want to find the length of the cycle and the list item that begins the cycle (the list item that has two inward pointers).

Your task is to modify both Floyd’s and Brent’s algorithms to find the length and location of a cycle. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

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: