реверсирование связанного списка в рубине с использованием стека

Question

Я реализую обратный связанный список, используя стек. Класс Stack имеет методы push и pop, которые превращают связанный список в стек, из которого может быть извлечен последний элемент, чтобы отменить порядок.

Я столкнулся с аналогичной ситуацией here, и я пытаюсь добавить метод к этому базовому корпусу. Я пытаюсь реализовать метод reverse_list, который использует Stack класс 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 

Я получаю ошибки при вызове Stack класса в reverse_list методе (undefined method push for <Context::LinkedListNode:0x00000001c5e0a8>).

Я в недоумении, почему я не могу использовать 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)

В вашем примере, переменная stack является экземпляром LinkedListNode, как push метод возвращает экземпляр связанного списка. Таким образом, ошибка метода не бросается. Вы должны создать экземпляр Stack сначала, как stack = Stack.new, который будет пустым стеком, а затем выполните операцию push и pop с помощью этого экземпляра.