Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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))
@nhocki

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 = 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
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.