Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

方法：先把linked list分成两半之后，reverse the second half。然后比较两半的node的值。
time complexity：O(n) space complexity：O(1)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head or not head.next: return True 
        
        slow = head 
        fast = head 
        
        while fast and fast.next and fast.next.next:
            slow = slow.next 
            fast = fast.next.next 
        
        p = slow.next
        slow.next = None 
        
        newHead = None 
        while p:
            _next = p.next 
            p.next = newHead
            newHead = p 
            p = _next 
            
        p1 = head 
        p2 = newHead 
        
        while p1 and p2:
            if p1.val != p2.val:
                return False 
            p1 = p1.next 
            p2 = p2.next 
            
        if not p1 and not p2:
            return True 
        if not p1 and p2 and not p2.next:
            return True 
        if not p2 and p1 and not p1.next:
            return True 
        
        return False