如何就地反转链表

Question

更新：我现在意识到我的问题应该是：如何通过 REFERENCE 传递参数？我在这里有一个线索：'pass parameter by reference' in Ruby? 但我不知道这是否可能。事实上可能值得关闭这个问题。

参考上一个问题：

我有点困惑为什么列表没有原地反转。

所以我的期望是： print_values(node3)

最初会给出： 12 -> 99 -> 37 -> nil

然后当我打电话时：reverse_list(node3)

我希望给 print_values(node3) 打电话给 37 -> 99 -> 12 -> nil

但是，我得到的是 12 -> nil

在某种程度上这是有道理的，因为 node3 引用的对象的值仍然为 12，并且 next_node 为 nil，但是有没有办法在 [=44 中完全反转列表=]?

关于可变性 w/r/t ruby 似乎有些东西我不太了解。就好像每次向内存 stack/function 调用添加新内容时，我们都会得到新对象？在这里做一些澄清将不胜感激。

我还创建了自己的方法来尝试使功能正常工作：

def reverse_list(list, previous=nil)

    rest_of_list = list.next_node
    print "rest of list: "
    print_values(rest_of_list)
    list.next_node = previous
    previous = list
    print "new previous: "
    print_values(previous)  
    list = rest_of_list
    print "new list: "
    print_values(list)
    if list.nil?
        print "list now nil\n"
        list = previous
        print "updated list: "
        print_values(list)
        return list
    else
        reverse_list(list, previous)
    end
end

Answer 1

回答您更新后的问题：

是的，您必须反转列表的值，而不是指针。

要执行此 AFAIK，您必须首先构建一个新的反向列表，然后将反向值复制回原始列表。

我已将原始代码更新为更多ruby-ish（即方法是列表的一部分class，“！”后缀用于指示该方法将修改对象（而不只是 return 一个新值。）

<script type="text/ruby">
def print(s)
  s = s.gsub("\n", "<br/>").gsub(" ", "&nbsp;")
  Element['#output'].html = Element['#output'].html + s
end

class LinkedListNode
  attr_accessor :value, :next_node

  def initialize(value, next_node=nil)
    @value = value
    @next_node = next_node
  end
 
  def reverse_list(reversed=nil)
    if next_node
      next_node.reverse_list(LinkedListNode.new(value, reversed))
    else
      LinkedListNode.new(value, reversed)
    end
  end
  
  def reverse_list!(list=self, reversed_list = reverse_list)
    self.value = reversed_list.value
    if next_node
      next_node.reverse_list!(list, reversed_list.next_node)
    else
      list
    end
  end
  
  def print_values
    print "[#{object_id}]#{value} --> "
    if next_node.nil?
      print "nil\n"
    else
      next_node.print_values
    end
  end
 
end

node1 = LinkedListNode.new(37)
node2 = LinkedListNode.new(99, node1)
node3 = LinkedListNode.new(12, node2)
print "original list:     "
node3.print_values
print "reversed list:     "
node3.reverse_list.print_values
print "reversed in place: "
node3.reverse_list!
node3.print_values

</script>


<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<script src="https://rawgit.com/reactrb/reactrb-express/master/reactrb-express.js"></script>
<div id="output" style="font-family: courier"></div>

Answer 2

Ruby

中没有引用传递

对于除最基本的类之外的所有内容（例如数字），都有一些方法可以就地修改对象，从而实现通过引用调用的大部分功能。

如何就地反转链表

How to reverse a LinkedList in place

ruby

linked-list

singly-linked-list