#class Node:
#  def __init__(self, value, next=None):
#    self.val = value
#    self.next = next
class Solution:
  def isPalindrome(self, head):
    
    def find_mid_node(head):
      slow, fast = head, head
      while fast:
        if fast.next:
          fast = fast.next.next
        else:
          break
        slow = slow.next
      mid = slow
      return mid
    
    def reverse_linked(node, stop):
      prev = None
      while node != stop:
        next_ = node.next
        node.next = prev
        prev = node
        node = next_
      return prev

    def check_palindrome(first, mid, last):
      is_palindrome = True
      while first and last and (first != mid or last != mid):
        if first.val != last.val:
          is_palindrome = False
          break
        else:
          first = first.next 
          last = last.next
      return is_palindrome
    
    first = head
    mid = find_mid_node(head)
    
    # reverse the linked list from the mid point to the end
    last = reverse_linked(mid, None)

    # palindrome checking
    is_palindrome = check_palindrome(first, mid, last)
    
    # de-reverse
    mid.next = reverse_linked(last, mid)

    return is_palindrome