Skip to content

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
You can’t perform that action at this time.