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)

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

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

it "should return true when 'is_cyclic' is called: last to middle" do
  middle = SingleLinkedListElement.new("middle")
  last = SingleLinkedListElement.new("last")
  last.next_node=middle
  add_elements(@list)
  @list.add(middle)
  add_elements(@list)
  @list.add(last)
  @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.

single_linked_list.rb

require 'single_linked_list_element'

class SingleLinkedList
  attr_reader :head

  def add(element)
    if @head.nil?
      @head = element
    else
      last_element=last()
      last_element.next_node=element
    end
  end

  def last()
    last_by_recursion(@head)
  end        

  def is_cyclic()
    if has_nil?(@head)
      false
    else
      @tortoise=@head
      @hare=@head.next_node.next_node
      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.

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
   Less Is More