如何在 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
"
    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屋！