Reverse a linked list

I got a phone interview with a tech company located in San Francisco Bay Area.

The interviewer questioned me about a linked list. I think that a linked list is basic but still can get really hard to answer in a short time under tremendous pressure.

The question goes:

Reverse any given linked list. For example, if a linked list A->B->C is given, return a new linked list C->B->A as an answer.

The interviewer gave me a hint that a simple loop is easier to program than recursion. After I struggled a lot, I came up with a rather clumsy solution. Probably, the interviewer wasn't very impressed.

I should have studied more about data structures...Well, "don't cry over split milk" though.

So today I have thought about a recursion version of the solution. I implemented it in Ruby. It took me quite a time (about 1 hour) to complete the code shown below. Please take a look if you are interested.

require 'test/unit'

class Node
  attr_accessor :value
  attr_accessor :next

  def initialize(value)
    self.value = value
  end

  def add(node)
    n = self
    until n.next.nil?
      n = n.next
    end  
    n.next = node
  end

  def self.from_array(a)
    return nil if a.nil? || a.size == 0
    list = nil 
    a.each do |value|
      if list.nil?
        list =  Node.new(value)
      else
        list.add(Node.new(value))
      end 
    end
    list
  end

  def to_array
    arr = []
    n = self
    until n.nil?
      arr.push(n.value)
      n = n.next
    end
    arr
  end 
end

# returns [head, tail]
def reverse_linked_list_impl(list)
  if list.next.nil?
    return [list, list]
  end
  head, tail = reverse_linked_list_impl(list.next)
  tail.next = list
  list.next = nil 
  return [head, list]
end

def reverse_linked_list(list)
  head, tail = reverse_linked_list_impl(list)
  return head
end

class TestAlgorithm < Test::Unit::TestCase
  def test_from_array
    list = Node.from_array([1, 2, 3])
    assert_equal(1, list.value)
    assert_equal(2, list.next.value)
    assert_equal(3, list.next.next.value)
  end

  def test_to_array
    list = Node.new(3)
    list.add(Node.new(5))
    list.add(Node.new(7))
    assert_equal([3, 5, 7], list.to_array) 
  end
  
  def test_reverse_linked_list
    arr = [1]    
    assert_equal(arr.reverse, reverse_linked_list(Node.from_array(arr)).to_array)
    arr = [1, 2]   
    assert_equal(arr.reverse, reverse_linked_list(Node.from_array(arr)).to_array)
    arr = [3, 1, 2]   
    assert_equal([2, 1, 3], reverse_linked_list(Node.from_array(arr)).to_array)
    arr = [5, 3, 1, 2]   
    assert_equal([2, 1, 3, 5], reverse_linked_list(Node.from_array(arr)).to_array)
 end

 end