如何在Ruby中反转链表

发布时间：2020-12-17 01:43:12 所属栏目：百科来源：网络整理

导读：在下面的变异示例中,我不明白链接列表是如何反转的. class LinkedListNode attr_accessor :value,:next_node def initialize(value,next_node=nil) @value = value @next_node = next_node endenddef print_values(list_node) print "#{list_node.value} --

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

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 "niln"
    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的值.我不明白什么是逆转清单.如果有人能向我解释这一点,我将不胜感激.

解决方法

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

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

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

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

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

nil <- 12 <- 99 <- 37 
                   ^

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!