スタックを使用してルビのリンクリストを逆転する

Question

スタックを使用して逆リンクリストを実装しています。 クラスStackには、リンクリストをスタックに変換するメソッドpushとpopがあり、そこから最後の要素を抽出して順序を逆転させることができます。

私は同様の状況hereに遭遇しました。そのベースケースにメソッドを追加しようとしています。私はreverse_listメソッドを実装しようとしていますクラスのpushとpopを使用して、ポインタを変更し、リンクされたリストを逆転させる方法。

これは私が試したものです：

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) 
    if list_node 
    print "#{list_node.value} --> " 
    print_values(list_node.next_node) 
    else  
    print "nil\n" 
    return 
    end 
end 

class Stack 
    attr_reader :data 

    def initialize 
     @data = nil 
    end 

    def push(value) 
     @data = LinkedListNode.new(value, @data) 
    end 

    def pop 
     return nil if @data.nil? 
     returning_value = @data.value 
     @data = @data.next_element 
     returning_value 
    end 
end 

def reverse_list(list) 
    stack = Stack.new.push(list.value) 
    list = list.next_node 

    while list 
     stack.push(list.value) 
     list = list.next_node 
    end 

    stack.pop 
end 

node1 = LinkedListNode.new(37) 
node2 = LinkedListNode.new(99, node1) 
node3 = LinkedListNode.new(12, node2) 

revlist = reverse_list(node3) 
print_values(revlist) 
# should return 37 --> 99 --> 12 --> nil 

reverse_list方法（undefined method push for <Context::LinkedListNode:0x00000001c5e0a8>）でStackクラスを呼び出すときに、私はエラーを取得します。

私はなぜStack,push、popの中でreverse_listを使用することができないのですか？私がreverse_listをどのように実装することができるかについてのヒントは、よく受け取ります。

Answer 1

以下がスタックに要素をプッシュし、それらを反転：

def reverse_list(list) 
    stack = Stack.new 

    while list 
     stack.push(list.value) 
     list = list.next_node 
    end 

    LinkedListNode.new(stack.pop, stack.data) 
end 

Answer 2

リストの最後までリストの内容をスタックに追加します。その後、以下のアルゴリズムを適用することができる。

root = stack.pop() # last element 
current = root 
while not stack.empty():  # move in reverse direction 
    current.next = stack.pop() # next element in stack is the next node 
    current = current.next  # continue to the next node 
current.next = nil    # mark end of the list 

Answer 3

スタック= Stack.new.push（list.value）

あなたの例でpush方法は、リンクされたリストのインスタンスを返すように、可変stackはLinkedListNodeのインスタンスです。だからメソッドエラーは投げていません。 stack = Stack.newのように最初にStackのインスタンスを作成し、空のスタックにしてからこのインスタンスを使用してプッシュ＆ポップ操作を行う必要があります。