Instantly share code, notes, and snippets.

# DiegoSalazar/scratch.rb

Last active February 3, 2017 05:26
Show Gist options
• Save DiegoSalazar/f27c199a3bc3fdbeaf95fa6feeea6a8d to your computer and use it in GitHub Desktop.
Implementation of Floyd's Cycle Detection Algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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 commented Feb 3, 2017 • edited Loading

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
``````

to join this conversation on GitHub. Already have an account? Sign in to comment