1find the middle of the list

2reverse the second half part

3compare the first and the reversed second part

```
class Solution(object):
def getListLength(self, head):
cnt = 0
while head:
head = head.next
cnt += 1
return cnt
def inverseHalfList(self, head, n):
# divide list into two parts, and inverse the second part
pre_idx = (n - 1) / 2 # pre pointer
pre = head
for i in range(pre_idx):
pre = pre.next
# inverse the rest list
# loop pre_idx-1 times
p = pre.next
for i in range(n - pre_idx - 2):
tmp = pre.next
pre.next = p.next
p.next = p.next.next
pre.next.next = tmp
return pre_idx, pre.next
def isPalindrome(self, head):
n = self.getListLength(head)
if n < 2:
return True
p = head
j, q = self.inverseHalfList(head, n)
# compare
for t in range(n - j - 1):
if p.val != q.val:
return False
p, q = p.next, q.next
return True
```