```
# 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
"""
# this problem cannot be solved in O(1) space complexity
# you have to remember the elts you saw before in an order
# different from how they appear in the list, which means
# you must store them in some info structure. inputs are rd-only !
# look before you leap
# head can be null
l1, l2, l3 = [], head, head.next if head != None else None
# l3 can be initially null because head can be null
# or head.next can be null
while l3 and l3.next:
l3 = (l3.next).next
l1.append(l2.val)
l2 = l2.next
# l3 can be null in case of an odd-length list
# or above conditions
# if len is odd, l3 is None and l2 is middle elt. skip it
# if len is odd, l3 is valid and l2 is middle elt. consider it
if l3 != None:
l1.append(l2.val)
# tricky details here
# consider [1]
# l3 is None, l1 is empty
# l2 is valid and first elt. move it
# l2 moves fwd in all cases
l2 = l2.next if l2 != None else None
while l2 != None:
if l1.pop() != l2.val:
return False
l2 = l2.next
return True
```