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

這是我編寫的一個小小的可視化。

^指向列表頭。在遞歸的每個級別，其右箭頭都是「轉向」，從右側的元素指向左側的元素。繼續進行，直到出現右箭頭（指向非零）。如果右箭頭指向零，則返回當前的頭部。

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 

由單向鏈表不一個普通的實踐ce（使用垃圾回收器的所有語言），通常有一個類（例如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]