ruby - 如何在 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 将是 下一个节点。返回下一行，

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 
                   ^