# Definition for singly-linked list.

 # class ListNode(object):

 #     def __init__(self, x):

 #         self.val = x

 #         self.next = None

 class Solution(object):

     def isPalindrome(self, head):

         """

         :type head: ListNode

         :rtype: bool

         """

         if head is None or head.next is None:

             return True

         slow = head

         quick = head

         while quick.next is not None:

             quick = quick.next

             if quick.next is not None:

                 quick = quick.next

                 slow = slow.next

         # Reverse sub list between slow.next and quick

         cur = slow.next

         slow.next = None

         then = cur.next

         cur.next = None

         while then is not None:

             tmp = then.next

             then.next = cur

             cur = then

             then = tmp

         second_head = cur

         # Compare first sub list and second sub list

         cur1 = head

         cur2 = second_head

         while cur1 is not None and cur2 is not None:

             if cur1.val != cur2.val:

                 return False

             cur1 = cur1.next

             cur2 = cur2.next

         return True