floyd_cycle_detection.rb

class LinkedListNode
  attr_accessor :value, :next_node

  def initialize(value, next_node=nil)
    @value = value
    @next_node = next_node
  end
end

def cycle_check(list_node)
  tortoise_pointer = list_node
  hare_pointer = list_node

  while list_node
    return false if hare_pointer.next_node.nil?
    hare_pointer = hare_pointer.next_node

    return false if hare_pointer.next_node.nil?
    hare_pointer = hare_pointer.next_node

    tortoise_pointer = tortoise_pointer.next_node

    return true if hare_pointer == tortoise_pointer
  end

  false
end

infinite_node1 = LinkedListNode.new(37)
infinite_node2 = LinkedListNode.new(99, infinite_node1)
infinite_node3 = LinkedListNode.new(6, infinite_node2)
infinite_node4 = LinkedListNode.new(23, infinite_node3)
infinite_node5 = LinkedListNode.new(4, infinite_node4)
infinite_node6 = LinkedListNode.new(36, infinite_node5)
infinite_node1.next_node = infinite_node6

puts "Infinity check on infinite list: #{cycle_check(infinite_node6)}"

puts "-------"

non_infinite_node1 = LinkedListNode.new(37)
non_infinite_node2 = LinkedListNode.new(99, non_infinite_node1)
non_infinite_node3 = LinkedListNode.new(12, non_infinite_node2)
non_infinite_node4 = LinkedListNode.new(55, non_infinite_node3)

puts "Infinity check on NON-infinite list: #{cycle_check(non_infinite_node3)}"

reversing_linked_list.rb

class LinkedListNode
  attr_accessor :value, :next_node

  def initialize(value, next_node=nil)
    @value = value
    @next_node = next_node
  end
end

class Stack
  attr_reader :data

  def initialize
    @data = nil
  end
  
  def push(element)
    @data = LinkedListNode.new(element, @data)
  end

  def pop
    old_data = @data
    @data = @data.next_node
    old_data
  end
end

def print_values(list_node)
  print "#{list_node.value} --> "
  if list_node.next_node.nil?
    print "nil\n"
    return
  else
    print_values(list_node.next_node)
  end
end

def reverse_list(list_node)
  stack = Stack.new

  while list_node
    stack.push(list_node.value)
    list_node = list_node.next_node
  end

  stack.pop
end

node1 = LinkedListNode.new(37)
node2 = LinkedListNode.new(99, node1)
node3 = LinkedListNode.new(12, node2)

print_values(node3)

puts "-------"

revlist = reverse_list(node3)

print_values(revlist)

reversing_linked_list_with_mutation.rb

class LinkedListNode
  attr_accessor :value, :next_node

  def initialize(value, next_node=nil)
    @value = value
    @next_node = next_node
  end
end

def print_values(list_node)
  print "#{list_node.value} --> "
  if list_node.next_node.nil?
    print "nil\n"
    return
  else
    print_values(list_node.next_node)
  end
end

def reverse_list(list_node, previous=nil)
  next_node = list_node.next_node
  list_node.next_node = previous
  if next_node
    reverse_list(next_node, list_node)
  else
    list_node
  end
end

node1 = LinkedListNode.new(37)
node2 = LinkedListNode.new(99, node1)
node3 = LinkedListNode.new(12, node2)

print_values(node3)

puts "-------"

revlist = reverse_list(node3)

print_values(revlist)