如何在Ruby中反转链表

Question

在下面的变异示例中,我不明白链接列表是如何反转的.

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)

如果我回来current_head,我会得到99->37->nil,这是有道理的,因为99会next_node.返回下一行,

list.next_node = previous

抛出错误,因为print_values方法无法打印值nil.我不明白什么是逆转清单.如果有人能向我解释这一点,我将不胜感激.

Answer 1

这是我编写的一点可视化.

^指向列表的头部.在每个递归级别,其右箭头"转向"从右侧的元素指向左侧的元素.继续,直到有一个右箭头(指向非零).如果右箭头指向nil,则返回当前头部.

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

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

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

nil <- 12 <- 99 <- 37 
                   ^