如何在Ruby中反向链接列表 [英] How to reverse a linked list in Ruby

问题描述

在下面的变异示例中，我不了解链表是如何反向的.

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)

如果我只返回 current_head ，则会得到 99-> 37-> nil ，这很有意义，因为 99 将是 next_node .返回下一行

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

引发错误，因为 print_values 方法无法打印 nil 的值.我不明白是什么在颠倒这个清单.如果有人可以向我解释这一点，我将不胜感激.

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.

推荐答案

这是我制作的一些可视化文件.

Here's a little visualization I made up.

^ 指向列表的开头.在递归的每个级别，其右箭头都会转向"，以从右侧的元素指向左侧的元素.继续直到出现右箭头(指向非零).如果右箭头指向nil，则返回当前头.

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

这篇关于如何在Ruby中反向链接列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！