How do you check if a linked list is a palindrome?

Combine three patterns. First, find the middle using slow and fast pointers. Second, reverse the second half of the list starting from the middle. Third, compare nodes from the head and from the reversed second half. If all corresponding values match, it is a palindrome. Optionally, re-reverse the second half to restore the original list. This runs in O of n time and O of one space. The alternative approach of copying values to an array and using two-pointer palindrome check uses O of n space, which interviewers may ask you to optimize away. ---