## Algorithmathon Day 2: Single Linked List Cycle

Created: 14 July 2013 Modified:The tail of a Single Linked List (SLL) can be found by working your way along the chain until the next node reference/pointer is null. What do you do if instead the last node points to another node such as the head? When a SLL tail (final node) points back to a previous node it is considered to be cyclic. If it does have a cycle how do we determine this? One way is to use The Tortoise and the Hare Algorithm.

Note: I have seen this condition referred to as cyclic and looped.

To solve our problem we will start with the SLL Base which can be found here. If you haven’t already read them, the rules for the Algorithmathon can be found here.

Lets add new RSpec tests for “is_cyclic”. The new tests will check for SSLs that end in nil, a tail that points to the head and a tail that points to the middle. The last two of which are cyclic.

single_linked_list_spec.rb (excerpt)

We can solve this problem by by using two object references. The tortoise will advance one link at a time and the hare will advance two links at a time. If there is a cycle then eventually the hare and the tortoise references will point to the same location. This is accomplished in the code below.

single_linked_list.rb

This code can be summed up in four simple rules.

- Tortoise advances one link at a time.
- Hare advances two links at a time.
- If you find a nil return false.
- If the hare and tortoise are in the same place return true.

There is more that one way to solve this problem and Ostermiller.org provides a good discussion of the solution options.

tags:*Algorithm*-

*Algorithmathon*-

*Cycle*-

*Cyclic*-

*Loop*-

*Looped*-

*RSpec*-

*Ruby*-

*Single Linked List*