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

Follow up:

  • Could you do it in O(n) time and O(1) space?


# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
# = None

class Solution(object):
    def isPalindrome(self, head):
        :type head: ListNode
        :rtype: bool
        if head is None:
            return True
        if is None:
            return True

        # Find the middle point of the string
        slow, fast = head,
        # True if number of elements is even
        even = True
        while is not None:
            fast =
            if is not None:
                fast =
                slow =
                even = False

        # Find the head of the 1st and 2nd half
        h1 = slow
        if even:
            h2 =
            h2 =

        # Reverse the linked list up to and including slow
        prev, curr, next = None, head,
        while curr != slow:
            next =
   = prev
            prev = curr
            curr = next = prev

        # Compare both half of the string
        while h2 is not None:
            if h1.val != h2.val:
                return False
                h1 =
                h2 =

        return True