Given a singly linked list, determine if it is a palindrome.
Could you do it in O(n) time and O(1) space?
The general idea is to partition the list into left and right parts. Reverse the one half list, it should be the same list as the other half. To partition, use slow and fast pointers and be careful about the boundary null pointers.