For about a year, I've always had a question I ask someone I'm interviewing for a programming position. I've asked this around 3 times and got some nice answers, but I had never implemented it. The question is really simple:

Given a linked list, how would you reverse it in O(n)?

Here's my solution:


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"

How would you do it? There's a really simple solution using a stack, but if you find another one, I'd love to hear about it on Twitter @nhocki