Instantly share code, notes, and snippets.

# nhocki/reverse_list.rb Created Dec 27, 2012

Reverse a list in O(n)
 Node = Struct.new(:id, :next) # Build the list first = Node.new(1, nil) nodes = 10.times.map{|x| Node.new(x + 2, nil)} nodes.each_with_index{|node, index| node.next = nodes[index + 1] } first.next = nodes.first def reverse_list(node) prox = node.next # Get the next node on the list. node.next = nil # Make the new tail point to nil (end of the new list). last = node # Save that new tail on a tmp variable (to point to it later) node = prox # Change the `current` node to the `next` one. Move ahead. while node # If I'm not at the end of the list. prox = node.next # Save the next node on the original list. node.next = last # Reverse the list (point back from `current`) last = node # Save the current node to point later. node = prox # Move ahead once. end last end def print_list(node) while node puts node.id node = node.next end end print_list(first) puts "\n" print_list(reverse_list(first))
Owner Author

### nhocki commented Dec 28, 2012

 Another approach is to use a `stack` to push everything first (and reverse it) and then rebuild the list. This will take twice the time but is still `O(n)` (`T(2n)`) ```def stack_it(node) stack = [] while node stack.unshift(node) # same as push node = node.next end # here, `stack` has the reversed list # so, we just need to re-build it prev = first = stack.shift while node = stack.shift prev.next = node prev = node end prev.next = nil # mark the new end of the list first # return the new first element end```
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.