1def assert_equals(x, y)
  2  raise [x, y].inspect unless x == y
  3end
  4
  5class ListNode
  6  attr_accessor :data, :next
  7
  8  def initialize(data)
  9    @data = data
 10    @next = nil
 11  end
 12
 13  def to_a
 14    current = self
 15    items = []
 16    while current
 17      items << current.data
 18      current = current.next
 19    end
 20    items
 21  end
 22
 23  def inspect
 24    print "["
 25    to_a.each { |current| print "(#{current})->" }
 26    puts "(nil)]"
 27  end
 28
 29  def to_s
 30    data.to_s
 31  end
 32end
 33
 34class Solution
 35  # time: O(2n) -> O(n)
 36  # space: O(n)
 37  def self.run(head)
 38    stack = []
 39    current = head
 40
 41    while current
 42      stack.push(current)
 43      current = current.next
 44    end
 45
 46    until stack.empty?
 47      c = stack.pop
 48      n = stack[-1]
 49      c.next = n
 50    end
 51  end
 52
 53=begin
 54         p
 55              c
 56                   n
 57                        t
 58[(nil)<-(4)<-(3)<-(2)->(1)->(0)->(nil)]
 59=end
 60  def self.swap(c, n, p)
 61    return if c.nil?
 62
 63    t = n&.next
 64    c.next = p
 65    n&.next = c
 66    swap(n, t, c)
 67  end
 68
 69  # time: O(n)
 70  # space: O(n)
 71  def self.run(head)
 72    swap(head, head.next, nil)
 73  end
 74end
 75
 76=begin
 77[(4)->(3)->(2)->(1)->(0)->(nil)]
 78
 79list
 80
 81   n     c    t
 82[(nil)<-(4)<-(3)<-(2)<-(1)<-(0) (nil)]
 83
 84# stack
 85
 86         c
 87           n
 88|0|1|2|3|4|
 89
 90until stack.empty?
 91  c = stack.pop
 92  n = stack.peek
 93  t = c.next
 94
 95  c.next = n
 96end
 97
 98=end
 99
100head = ListNode.new(4)
101node1 = ListNode.new(3)
102node2 = ListNode.new(2)
103node3 = ListNode.new(1)
104tail = ListNode.new(0)
105
106head.next = node1
107node1.next = node2
108node2.next = node3
109node3.next = tail
110
111puts head.inspect
112assert_equals(head.to_a, [4,3,2,1,0])
113Solution.run(head)
114puts tail.inspect
115assert_equals(tail.to_a, [0,1,2,3,4])