14 July 2013

Algorithmathon

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.

``````it "should return true when 'is_cyclic' is called: last to first" do
last.next_node=first
@list.is_cyclic().should be_true
end

it "should return false when 'is_cyclic' is called: nil terminated" do
@list.is_cyclic().should be_false
end

it "should return true when 'is_cyclic' is called: last to middle" do
last.next_node=middle
@list.is_cyclic().should be_true
end``````

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.

``````require 'single_linked_list_element'

else
last_element=last()
last_element.next_node=element
end
end

def last()
end

def is_cyclic()
false
else
is_cyclic_recursion()
end
end

private
def last_by_recursion(element)
unless element.nil?
unless element.next_node.nil?
last_by_recursion(element.next_node)
else
element
end
end
end

def is_cyclic_recursion()
if @tortoise.eql?(@hare)
true
else
if has_nil?(@tortoise) || has_nil?(@hare)
false
else
@tortoise=@tortoise.next_node
@hare=@hare.next_node.next_node
is_cyclic_recursion()
end
end

end

def has_nil?(element)
element.nil? || element.next_node.nil? || element.next_node.next_node.nil?
end

end``````

This code can be summed up in four simple rules.