如何在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 "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的值，因此引发错误。我不明白是什么推翻了这份清单。如果有人能向我解释这一点，我将不胜感激。

Answer 1

下面是我制作的一个小可视化。

^指向列表的头部。在每一级递归中，它的右箭头都会"旋转"，从右边的元素指向左边的元素。继续操作，直到出现向右箭头（指向非零）。如果向右箭头指向零，则返回当前头。

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(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(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(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）具有您可能需要的所有功能和灵活性。

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]