Skip to content

Instantly share code, notes, and snippets.

@DiegoSalazar DiegoSalazar/scratch.rb

Last active Feb 3, 2017
Embed
What would you like to do?
Implementation of Floyd's Cycle Detection Algorithm
class Node
attr_reader :value
attr_accessor :next_node
def initialize(value, next_node = nil)
@value = value
@next_node = next_node
end
def end?
next_node.nil?
end
def ==(node)
node.value == value
end
end
class Floyd
def initialize(node)
@tortoise = node
@hare = node
end
def cycle?
loop do
return if @hare.end?
@hare = @hare.next_node
return if @hare.end?
@hare = @hare.next_node
@tortoise = @tortoise.next_node
return true if @hare == @tortoise
end
end
end
# Linked List #3: (optional) Floyd's Cycle Detection Algorithm
n1 = Node.new(1, Node.new(2, Node.new(3)))
puts "List 1: #{Floyd.new(n1).cycle? ? "Has cycle" : "No cycle"}"
looped1 = Node.new 1
looped2 = Node.new 2
looped3 = Node.new 3
looped1.next_node = looped2
looped2.next_node = looped3
looped3.next_node = looped1
puts "List 2: #{Floyd.new(looped3).cycle? ? "Has cycle" : "No cycle"}"
@DiegoSalazar

This comment has been minimized.

Copy link
Owner Author

DiegoSalazar commented Feb 3, 2017

Output:

[Running] ruby "/Users/diego/Desktop/scratch.rb"
List 1: No cycle
List 2: Has cycle

[Done] exited with code=0 in 0.039 seconds
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.