Reverse a list in O(n)

reverse_list.rb

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))

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