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