def assert_equals(x, y)
  raise [x, y].inspect unless x == y
end

class ListNode
  attr_accessor :data, :next

  def initialize(data)
    @data = data
    @next = nil
  end

  def to_a
    current = self
    items = []
    while current
      items << current.data
      current = current.next
    end
    items
  end

  def inspect
    print "["
    to_a.each { |current| print "(#{current})->" }
    puts "(nil)]"
  end

  def to_s
    data.to_s
  end
end

class Solution
  # time: O(2n) -> O(n)
  # space: O(n)
  def self.run(head)
    stack = []
    current = head

    while current
      stack.push(current)
      current = current.next
    end

    until stack.empty?
      c = stack.pop
      n = stack[-1]
      c.next = n
    end
  end

=begin
         p
              c
                   n
                        t
[(nil)<-(4)<-(3)<-(2)->(1)->(0)->(nil)]
=end
  def self.swap(c, n, p)
    return if c.nil?

    t = n&.next
    c.next = p
    n&.next = c
    swap(n, t, c)
  end

  # time: O(n)
  # space: O(n)
  def self.run(head)
    swap(head, head.next, nil)
  end
end

=begin
[(4)->(3)->(2)->(1)->(0)->(nil)]

list

   n     c    t
[(nil)<-(4)<-(3)<-(2)<-(1)<-(0) (nil)]

# stack

         c
           n
|0|1|2|3|4|

until stack.empty?
  c = stack.pop
  n = stack.peek
  t = c.next

  c.next = n
end

=end

head = ListNode.new(4)
node1 = ListNode.new(3)
node2 = ListNode.new(2)
node3 = ListNode.new(1)
tail = ListNode.new(0)

head.next = node1
node1.next = node2
node2.next = node3
node3.next = tail

puts head.inspect
assert_equals(head.to_a, [4,3,2,1,0])
Solution.run(head)
puts tail.inspect
assert_equals(tail.to_a, [0,1,2,3,4])