Instantly share code, notes, and snippets.

What would you like to do?
Reverse a list in O(n)
Node =, :next)
# Build the list
first =, nil)
nodes ={|x| + 2, nil)}
nodes.each_with_index{|node, index| = nodes[index + 1] } = nodes.first
def reverse_list(node)
prox = # Get the next node on the list. = 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 = # Save the next node on the original list. = last # Reverse the list (point back from `current`)
last = node # Save the current node to point later.
node = prox # Move ahead once.
def print_list(node)
while node
node =
puts "\n"

This comment has been minimized.

Copy link
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 =

  # here, `stack` has the reversed list
  # so, we just need to re-build it

  prev = first = stack.shift
  while node = stack.shift = node
    prev = node
  end = nil # mark the new end of the list
  first  # return the new first element
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment