# Question

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


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

# Solution

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

class Solution(object):
"""
:rtype: bool
"""
return True
return True

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

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

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

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

return True