如何在Ruby中反转链表

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

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 ^ 

Answer 2

 # Create a LinkedListNode instance with value 36 node1 = LinkedListNode.new(37) # Create a LinkedListNode instance which next value is node1 node2 = LinkedListNode.new(99, node1) # node2 -> node1 # Create a LinkedListNode instance which next value is node2 node3 = LinkedListNode.new(12, node2) # node3 -> node2 -> node1 print_values(node3) # 12 -> 99 -> 37 

拳头传递给reverse_list方法

 reverse_list(node3) def reverse_list(list, previous=nil) # set current_head to node2 current_head = list.next_node # Change node3.next_node node2-->nil list.next_node = previous if current_head # reverse_list(node2, node3) reverse_list(current_head, list) else list end end 

第二次进入reverse_list方法

 reverse_list(node2, node3) def reverse_list(list, previous=nil) # set current_head to node1 current_head = list.next_node # Change node2.next_node node1-->node3 list.next_node = previous if current_head # reverse_list(node1, node2) reverse_list(current_head, list) else list end end 

最后进入reverse_list方法

 reverse_list(node1, node2) def reverse_list(list, previous=nil) # set current_head to nil current_head = list.next_node # Change node1.next_node nil-->node2 list.next_node = previous if current_head reverse_list(current_head, list) else # The end, return node1 list end end 

顺便说一下，链表不是ruby语言中的常见做法（以及带有垃圾收集器的所有语言），通常有一个类（例如Array），它具有您可能需要的所有function和灵活性。

Answer 3

如果有人希望在没有递归的情况下执行此操作，这是一个简单的解决方案

 class Node attr_accessor :value, :next def initialize(value, next_node) @value = value @next = next_node end end class LinkedList attr_accessor :head, :tail def add(value) if(@head.nil?) @head = Node.new(value, nil) @tail = @head else @tail.next = Node.new(value, nil) @tail = @tail.next end end def reverse(list) return nil if list.nil? prev = nil curr = list.head while(curr != nil) temp = curr.next curr.next = prev prev = curr curr = temp end list.head = prev list end def display(list) return nil if list.nil? curr = list.head arr = [] while(curr != nil) arr.push(curr.value) curr = curr.next end p arr end end list = LinkedList.new() list.add(1) list.add(2) list.add(3) list.display(list) #list before reversing [1,2,3] list.display(list.reverse(list)) #list after reversing [3,2,1]