How to reverse a linked list in Ruby

Question

In the mutation example below, I don't understand how the linked list is reversed.

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, previous=nil)
  current_head = list.next_node
  list.next_node = previous
  if current_head
    reverse_list(current_head, list)
  else
    list
  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)

If I just return current_head, I get 99->37->nil, which makes sense because 99 would be next_node. Returning the next line,

list.next_node = previous

throws an error because print_values method can't print the value for nil. I'm not understanding what is reversing the list. If anyone could explain this to me, I would appreciate it.

Answer 1

Here's a little visualization I made up.

^ points to head of the list. At each level of recursion, its right arrow is "turned" to point from element on the right to element on the left. Proceed until there is a right arrow (pointing to a non-nil). If right arrow points to nil, return the current head.

previous
↓
nil    12 -> 99 -> 37 -> nil
       ^

       previous
       ↓ 
nil <- 12       99 -> 37 -> nil
                ^

             previous
             ↓
nil <- 12 <- 99       37 -> nil
                      ^         

nil <- 12 <- 99 <- 37 
                   ^                            

Answer 2

# Create a LinkedListNode instance with value 36
node1 = LinkedListNode.new(37)
# Create a LinkedListNode instance which next value is node1
node2 = LinkedListNode.new(99, node1)
# node2 -> node1
# Create a LinkedListNode instance which next value is node2
node3 = LinkedListNode.new(12, node2)
# node3 -> node2 -> node1

print_values(node3)
# 12 -> 99 -> 37

Fist pass into reverse_list method

reverse_list(node3)
def reverse_list(list, previous=nil)
  # set current_head to node2
  current_head = list.next_node
  # Change node3.next_node node2-->nil
  list.next_node = previous
  if current_head
    # reverse_list(node2, node3)
    reverse_list(current_head, list)
  else
    list
  end
end

Second pass into reverse_list method

reverse_list(node2, node3)
def reverse_list(list, previous=nil)
  # set current_head to node1
  current_head = list.next_node
  # Change node2.next_node node1-->node3
  list.next_node = previous
  if current_head
    # reverse_list(node1, node2)
    reverse_list(current_head, list)
  else
    list
  end
end

last pass into reverse_list method

reverse_list(node1, node2)
def reverse_list(list, previous=nil)
  # set current_head to nil
  current_head = list.next_node
  # Change node1.next_node nil-->node2
  list.next_node = previous
  if current_head
    reverse_list(current_head, list)
  else
    # The end, return node1
    list
  end
end

By the way linked list is not a common practice in the ruby languages (and all the languages with a garbage collector), there is generally a class (such as Array for example) which have all the functionalities and flexibility you may need.