Cycle detector

cycle-detection-example.rb

class Node
  attr_accessor :next

  def initialize(nxt)
    @next = nxt
  end

  def self.linked_list_with_cycle
    node = linked_list_without_cycle
    node.next.next.next = node
  end

  def self.linked_list_without_cycle
    node3 = new(nil)
    node2 = new(node3)
    new(node2)
  end
end

# Using https://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare
def cycle?(node)
  slow = node
  fast = node

  loop do
    slow = slow.next
    fast = fast.try(:next).try(:next)
    return false if slow.nil? || fast.nil?
    return true if slow == fast
  end
end

# "Tests"

if cycle?(Node.linked_list_with_cycle) == true
  puts "Hurray!"
else
  puts "Booo"
end

if cycle?(Node.linked_list_without_cycle) == false
  puts "Hurray!"
else
  puts "Booo"
end