1<<-DOC
  2Given a singly linked list of integers, determine whether or not it's a palindrome.
  3
  4Example
  5
  6For l = [0, 1, 0], the output should be
  7isListPalindrome(l) = true;
  8For l = [1, 2, 2, 3], the output should be
  9isListPalindrome(l) = false.
 10Input/Output
 11
 12[time limit] 4000ms (rb)
 13[input] linkedlist.integer l
 14
 15A singly linked list of integers.
 16
 17Guaranteed constraints:
 180 ≤ list size ≤ 5 · 10^5,
 19-10^9 ≤ element value ≤ 10^9.
 20
 21[output] boolean
 22
 23Return true if l is a palindrome, otherwise return false.
 24DOC
 25
 26describe "is_list_palindrome" do
 27  def palindrome?(head)
 28    return true if head.nil?
 29
 30    length = length_of(head)
 31    mid = length.even? ? length / 2 : (length / 2) + 1
 32    distance_travelled = 0
 33    left_sum, right_sum = 0, 0
 34
 35    node = head
 36    until node.nil?
 37      if distance_travelled >= mid
 38        right_sum += node.value
 39      else
 40        left_sum += node.value
 41      end
 42      distance_travelled += 1
 43      node = node.next
 44    end
 45
 46    if length.even?
 47      left_sum - right_sum == 0
 48    else
 49      left_sum - right_sum == 1
 50    end
 51  end
 52
 53  def length_of(head)
 54    n = 1
 55    n += 1 while head = head.next
 56    n
 57  end
 58
 59  # recursion blows the stack for a long list
 60  #def advance_to(head, index)
 61    #return head if index == 0
 62    #advance_to(head.next, index - 1)
 63  #end
 64
 65  def advance_to(head, index)
 66    return head if index == 0
 67    (index - 1).downto(0) do |n|
 68      head = head.next
 69    end
 70    head
 71  end
 72
 73  def reverse(head)
 74    new_root = nil
 75    root = head
 76
 77    while root
 78      next_node = root.next
 79      root.next = new_root
 80      new_root = root
 81      root = next_node
 82    end
 83    new_root
 84  end
 85
 86  def palindrome?(head)
 87    return true if head.nil?
 88    length = length_of(head)
 89    mid = length / 2
 90
 91    x, y = head, reverse(advance_to(head, mid))
 92    0.upto(mid - 1) do |i|
 93      return false unless x.value == y.value
 94      x, y = x.next, y.next
 95    end
 96    true
 97  end
 98
 99  class ListNode
100    attr_accessor :value, :next
101
102    def initialize(value, next_node: nil)
103      @value = value
104      @next = next_node
105    end
106
107    def to_a
108      result = []
109      current = self
110      until current.nil?
111        result.push(current.value)
112        current = current.next
113      end
114      result
115    end
116  end
117
118  def to_list(items)
119    x = nil
120    items.inject(nil) do |memo, item|
121      node = ListNode.new(item)
122      if memo.nil?
123        x = node
124      else
125        memo.next = node
126      end
127      node
128    end
129    x
130  end
131
132  [
133    { l: [0, 1, 0], x: true },
134    { l: [1, 2, 2, 3], x: false },
135    { l: [1, 1000000000, -1000000000, -1000000000, 1000000000, 1], x: true },
136    { l: [1, 2, 3, 3, 2], x: false },
137    { l: [1, 2, 3, 1, 2, 3], x: false },
138    { l: [], x: true },
139    { l: [3, 5, 3, 5], x: false },
140    { l: [1, 5, 2, 4], x: false },
141    { l: [10], x: true },
142    { l: [0, 0], x: true },
143    { l: [1, 3, 2, 2, 2], x: false },
144  ].each do |x|
145    it do
146      expect(palindrome?(to_list(x[:l]))).to eql(x[:x])
147    end
148  end
149end